| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 35320 |
2017-11-20T07:59:34 Z |
cheater2k |
코알라 (JOI13_koala) |
C++14 |
|
63 ms |
5332 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100020;
const long long inf = 1e18;
int K, M, D, A, N;
vector<int> z;
int T[MAX], B[MAX];
long long T1[MAX], T2[MAX];
void upd1(int x, long long v) { for (; x < MAX; x += x & -x) T1[x] = min(T1[x], v); }
long long get1(int x) { long long res = inf; for (; x > 0; x -= x & -x) res = min(res, T1[x]); return res; }
void upd2(int x, long long v) { for (; x > 0; x -= x & -x) T2[x] = min(T2[x], v); }
long long get2(int x) { long long res = inf; for (; x < MAX; x += x & -x) res = min(res, T2[x]); return res; }
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> K >> M >> D >> A >> N;
z.push_back(0);
for (int i = 1; i <= N; ++i) {
cin >> T[i] >> B[i]; T[i] -= K;
z.push_back(T[i] % D);
}
M -= K; T[N + 1] = M; z.push_back(M % D);
sort(z.begin(), z.end());
z.resize(distance(z.begin(), unique(z.begin(), z.end())));
for (int i = 0; i < MAX; ++i) T1[i] = T2[i] = inf;
upd1(1, 0);
upd2(1, 0);
long long f;
for (int i = 1; i <= N + 1; ++i) {
int md = lower_bound(z.begin(), z.end(), T[i] % D) - z.begin() + 1;
f = 1LL * (T[i] / D) * A - B[i] + get2(md);
f = min(f, 1LL * (T[i] / D) * A + A - B[i] + get1(md - 1));
upd1(md, f - 1LL * (T[i] / D) * A);
upd2(md, f - 1LL * (T[i] / D) * A);
}
cout << -f << '\n';
}
Compilation message
koala.cpp: In function 'int main()':
koala.cpp:43:11: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
cout << -f << '\n';
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4524 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4524 KB |
Output is correct |
| 3 |
Correct |
0 ms |
4524 KB |
Output is correct |
| 4 |
Correct |
0 ms |
4524 KB |
Output is correct |
| 5 |
Correct |
0 ms |
4524 KB |
Output is correct |
| 6 |
Correct |
0 ms |
4524 KB |
Output is correct |
| 7 |
Correct |
0 ms |
4524 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4524 KB |
Output is correct |
| 9 |
Correct |
0 ms |
4524 KB |
Output is correct |
| 10 |
Correct |
0 ms |
4524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
5332 KB |
Output is correct |
| 2 |
Correct |
39 ms |
5332 KB |
Output is correct |
| 3 |
Correct |
23 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
43 ms |
5332 KB |
Output is correct |
| 5 |
Correct |
23 ms |
4944 KB |
Output is correct |
| 6 |
Correct |
16 ms |
4944 KB |
Output is correct |
| 7 |
Correct |
29 ms |
5332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
5332 KB |
Output is correct |
| 2 |
Correct |
53 ms |
5332 KB |
Output is correct |
| 3 |
Correct |
46 ms |
5332 KB |
Output is correct |
| 4 |
Correct |
53 ms |
5332 KB |
Output is correct |
| 5 |
Correct |
46 ms |
4944 KB |
Output is correct |
| 6 |
Correct |
26 ms |
4944 KB |
Output is correct |
