| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12938 |
2015-01-21T04:59:08 Z |
model_code |
코알라 (JOI13_koala) |
C++ |
|
84 ms |
6364 KB |
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
using namespace std;
typedef unsigned uint;
typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair
template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }
const Int INF = 1001001001001001001LL;
const int LIM_N = 100000;
int K, M, D;
Int A;
int N;
int T[LIM_N + 10];
Int B[LIM_N + 10];
int xsLen;
int xs[LIM_N + 10];
int getPos(int x) {
return lower_bound(xs, xs + xsLen, x) - xs;
}
int segN;
Int seg[LIM_N * 4 + 10];
void init(int n) {
for (segN = 1; segN < n; segN <<= 1);
int a;
for (a = segN * 2; --a; ) seg[a] = -INF;
}
void update(int a, Int val) {
for (a += segN; a; a >>= 1) {
chmax(seg[a], val);
}
}
Int rangeMax(int a, int b) {
Int ret = -INF;
for (a += segN, b += segN; a <= b; a >>= 1, b >>= 1) {
if ( a & 1) { chmax(ret, seg[a]); ++a; }
if (~b & 1) { chmax(ret, seg[b]); --b; }
}
return ret;
}
int main() {
int i;
K = in();
M = in();
D = in();
A = in();
N = in();
for (i = 0; i < N; ++i) {
T[i] = in();
B[i] = in();
}
T[N] = M;
B[N] = 0;
xsLen = 0;
xs[xsLen++] = K % D;
xs[xsLen++] = M % D;
for (i = 0; i < N; ++i) {
xs[xsLen++] = T[i] % D;
}
sort(xs, xs + xsLen);
xsLen = unique(xs, xs + xsLen) - xs;
init(xsLen);
update(getPos(K % D), 0);
for (i = 0; i <= N; ++i) {
int pos = getPos(T[i] % D);
Int tmp = -INF;
chmax(tmp, rangeMax(0, pos - 1) - A);
chmax(tmp, rangeMax(pos, xsLen - 1));
tmp += B[i];
update(pos, tmp);
if (i == N) {
Int ans = tmp - (M / D - K / D) * A;
printf("%lld\n", ans);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
6364 KB |
Output is correct |
| 6 |
Correct |
0 ms |
6364 KB |
Output is correct |
| 7 |
Correct |
0 ms |
6364 KB |
Output is correct |
| 8 |
Correct |
0 ms |
6364 KB |
Output is correct |
| 9 |
Correct |
0 ms |
6364 KB |
Output is correct |
| 10 |
Correct |
0 ms |
6364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
6364 KB |
Output is correct |
| 2 |
Correct |
44 ms |
6364 KB |
Output is correct |
| 3 |
Correct |
20 ms |
6364 KB |
Output is correct |
| 4 |
Correct |
48 ms |
6364 KB |
Output is correct |
| 5 |
Correct |
20 ms |
6364 KB |
Output is correct |
| 6 |
Correct |
16 ms |
6364 KB |
Output is correct |
| 7 |
Correct |
32 ms |
6364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
6364 KB |
Output is correct |
| 2 |
Correct |
84 ms |
6364 KB |
Output is correct |
| 3 |
Correct |
76 ms |
6364 KB |
Output is correct |
| 4 |
Correct |
72 ms |
6364 KB |
Output is correct |
| 5 |
Correct |
48 ms |
6364 KB |
Output is correct |
| 6 |
Correct |
32 ms |
6364 KB |
Output is correct |
