| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26874 |
2017-07-06T17:39:05 Z |
abcdef6199 |
코알라 (JOI13_koala) |
C++ |
|
153 ms |
7916 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> II;
const int MAXN = (int) 1e5 + 10;
int n, d, cost, a[MAXN], b[MAXN], c[MAXN];
LL dp[MAXN];
#define mid ((l + r) >> 1)
const LL INF = 1e18;
struct SegTree {
LL S[MAXN * 5];
void Build(int k, int l, int r) {
if (l == r) {
S[k] = -INF;
return;
}
Build(k << 1 | 0, l, mid);
Build(k << 1 | 1, mid + 1, r);
S[k] = max(S[k << 1], S[k << 1 | 1]);
}
void Update(int k, int l, int r, int i, LL v) {
if (l == r) {
S[k] = v;
return;
}
if (i <= mid) Update(k << 1, l, mid, i, v);
else Update(k << 1 | 1, mid + 1, r, i, v);
S[k] = max(S[k << 1], S[k << 1 | 1]);
}
LL Query(int k, int l, int r, int i, int j) {
if (l > j || r < i) return -INF;
if (i <= l && r <= j) return S[k];
return max(Query(k << 1, l, mid, i, j), Query(k << 1 | 1, mid + 1, r, i, j));
}
} ST;
#undef mid
int main() {
int s, t; scanf("%d%d", &s, &t);
scanf("%d%d%d", &d, &cost, &n); n += 2;
for (int i = 2; i <= n - 1; ++i) scanf("%d%d", &a[i], &b[i]);
a[1] = s; b[1] = 0;
a[n] = t; b[n] = 0;
for (int i = 1; i <= n; ++i) c[i] = a[i] % d;
sort(c + 1, c + 1 + n);
ST.Build(1, 1, n);
for (int i = 1; i <= n; ++i) {
if (i > 1) {
int pos = lower_bound(c + 1, c + 1 + n, a[i] % d) - c;
LL f1 = ST.Query(1, 1, n, 1, pos - 1) - cost;
LL f2 = ST.Query(1, 1, n, pos, n);
dp[i] = max(f1, f2) - cost * LL(a[i] / d) + b[i];
}
ST.Update(1, 1, n, lower_bound(c + 1, c + 1 + n, a[i] % d) - c, dp[i] + cost * LL(a[i] / d));
}
// for (int i = 1; i <= n; ++i) cout << dp[i] << " "; cout << endl;
cout << dp[n];
return 0;
}
Compilation message
koala.cpp: In function 'int main()':
koala.cpp:42:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int s, t; scanf("%d%d", &s, &t);
^
koala.cpp:43:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &d, &cost, &n); n += 2;
^
koala.cpp:44:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 2; i <= n - 1; ++i) scanf("%d%d", &a[i], &b[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
7916 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7916 KB |
Output is correct |
| 3 |
Correct |
0 ms |
7916 KB |
Output is correct |
| 4 |
Correct |
0 ms |
7916 KB |
Output is correct |
| 5 |
Correct |
0 ms |
7916 KB |
Output is correct |
| 6 |
Correct |
0 ms |
7916 KB |
Output is correct |
| 7 |
Correct |
0 ms |
7916 KB |
Output is correct |
| 8 |
Correct |
0 ms |
7916 KB |
Output is correct |
| 9 |
Correct |
0 ms |
7916 KB |
Output is correct |
| 10 |
Correct |
0 ms |
7916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
7916 KB |
Output is correct |
| 2 |
Correct |
119 ms |
7916 KB |
Output is correct |
| 3 |
Correct |
29 ms |
7916 KB |
Output is correct |
| 4 |
Correct |
96 ms |
7916 KB |
Output is correct |
| 5 |
Correct |
43 ms |
7916 KB |
Output is correct |
| 6 |
Correct |
29 ms |
7916 KB |
Output is correct |
| 7 |
Correct |
53 ms |
7916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
7916 KB |
Output is correct |
| 2 |
Correct |
153 ms |
7916 KB |
Output is correct |
| 3 |
Correct |
129 ms |
7916 KB |
Output is correct |
| 4 |
Correct |
116 ms |
7916 KB |
Output is correct |
| 5 |
Correct |
93 ms |
7916 KB |
Output is correct |
| 6 |
Correct |
66 ms |
7916 KB |
Output is correct |
