-
Notifications
You must be signed in to change notification settings - Fork 11
/
kattis_sellingspatulas.cpp
74 lines (66 loc) · 2.4 KB
/
kattis_sellingspatulas.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/* Kattis - sellingspatulas
This problem is simple in theory, but I found alot of problem when trying to use integers to
represent the profits.
After some extensive testing, the problem was a rounding error when converting 2dp float to int
Instead of just "cur = cur*100", we should use "cur = roundf(cur * 100)" to round to nearest
incase theres some floating point precision error!
Anyway, the solution is just kadane without much changes. Except to select the answer not just
based on value but also based on duration and start time.
Time: O(1440), Space: O(1440)
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define EPS 1e-9
#define double_equal(a, b) (abs(a - b) <= EPS)
int n, t;
double cur;
vector<double> ori;
int main() {
while (true) {
scanf("%d", &n);
if (n == 0) break;
ori.assign(1440, -0.08);
for (int i = 0; i < n; i++) {
scanf("%d %le", &t, &cur);
ori[t] += cur;
}
// Kadane's Algorithm on Ori
double sum = 0, ans = 0;
int sum_start = 0, sum_duration = 0, ans_start = 0, ans_duration = 0;
for (int i = 0; i < 1440; i++) {
sum += ori[i];
// cout << sum <<endl;
if (sum < EPS) { // better to reset sum
sum = 0;
sum_start = i + 1;
sum_duration = 0;
} else { // extend sum to current value
sum_duration++;
}
// Check if current sum is a better answer
if (sum - ans > EPS) {
// if strictly less than
ans = sum;
ans_start = sum_start;
ans_duration = sum_duration;
} else if (double_equal(ans, sum)) {
// check if our time_period is shorter or not if equal
if (sum_duration < ans_duration) {
// sum period is shorter
ans_start = sum_start;
ans_duration = sum_duration;
}
}
// else we take the earlier one, ie no change
}
if (double_equal(0, ans)) {
cout << "no profit" << endl;
} else {
printf("%.2f %d %d\n", ans, ans_start, ans_start + ans_duration - 1);
}
}
return 0;
}