# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
131038 | 2019-07-16T11:52:39 Z | imyujin | Bodyguards (CEOI10_bodyguards) | C++14 | 169 ms | 19348 KB |
#include <stdio.h> #include <vector> #include <algorithm> #include <functional> using namespace std; #define MAXR 200005 #define fi first #define se second typedef long long lint; typedef pair<int, int> pii; typedef pair<lint, lint> pll; vector<pll> rv, cv; int main() { int R, C; scanf("%d", &R); rv.resize(R); for(int i = 0; i < R; i++) scanf("%lld%lld", &rv[i].fi, &rv[i].se); scanf("%d", &C); cv.resize(C); for(int i = 0; i < C; i++) scanf("%lld%lld", &cv[i].fi, &cv[i].se); lint sumr = 0, sumc = 0; for(int i = 0; i < R; i++) sumr += rv[i].fi * rv[i].se; for(int i = 0; i < C; i++) sumc += cv[i].fi * cv[i].se; if(sumr != sumc) { printf("0"); return 0; } rv.push_back(make_pair(1ll << 30, 0)); sort(rv.begin(), rv.end(), greater<pll>()); sort(cv.begin(), cv.end(), greater<pll>()); vector<pll> v; for(int i = 0; i < cv.size(); i++) { if(i > 0 && cv[i - 1].fi == cv[i].fi) v.back().se += cv[i].se; else v.push_back(cv[i]); } swap(cv, v); for(int i = 1; i < cv.size(); i++) cv[i].se += cv[i - 1].se; rv[0].fi = rv[0].fi * rv[0].se; for(int i = 1; i < rv.size(); i++) { rv[i].fi = rv[i - 1].fi + rv[i].fi * rv[i].se; rv[i].se += rv[i - 1].se; } /* for(int i = 0; i < cv.size(); i++) printf("(%lld, %lld)", cv[i].fi, cv[i].se); printf("\n"); for(int i = 0; i < rv.size(); i++) printf("(%lld, %lld)", rv[i].fi, rv[i].se); printf("\n"); */ lint A = 0ll, h = 0ll; int p = cv.size() - 1; for(int i = 1; i < rv.size(); i++) { //printf("h = %lld, A = %lld, p = %d\n", h, A, p); if(A + cv[p].se < rv[i - 1].fi + (rv[i].fi - rv[i - 1].fi) / rv[i].se) { printf("0"); return 0; } while(p >= 0 && cv[p].fi <= rv[i].se) { A += (cv[p].fi - h) * cv[p].se; h = cv[p].fi; p--; } if(p < 0) break; A += (rv[i].se - h) * cv[p].se; h = rv[i].se; if(A < rv[i].fi) { printf("0"); return 0; } } printf("1"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 380 KB | Output is correct |
4 | Correct | 2 ms | 380 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 256 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 256 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 256 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 256 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 256 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 256 KB | Output is correct |
9 | Correct | 2 ms | 256 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 380 KB | Output is correct |
14 | Correct | 2 ms | 256 KB | Output is correct |
15 | Correct | 2 ms | 380 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 256 KB | Output is correct |
18 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 3 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 376 KB | Output is correct |
18 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 380 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 380 KB | Output is correct |
18 | Correct | 3 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 252 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 252 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 256 KB | Output is correct |
8 | Correct | 2 ms | 256 KB | Output is correct |
9 | Correct | 2 ms | 256 KB | Output is correct |
10 | Correct | 2 ms | 256 KB | Output is correct |
11 | Correct | 2 ms | 256 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Correct | 2 ms | 380 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 2 ms | 256 KB | Output is correct |
18 | Correct | 2 ms | 380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 632 KB | Output is correct |
2 | Correct | 4 ms | 508 KB | Output is correct |
3 | Correct | 4 ms | 504 KB | Output is correct |
4 | Correct | 4 ms | 508 KB | Output is correct |
5 | Correct | 5 ms | 504 KB | Output is correct |
6 | Correct | 5 ms | 632 KB | Output is correct |
7 | Correct | 5 ms | 632 KB | Output is correct |
8 | Correct | 5 ms | 504 KB | Output is correct |
9 | Correct | 6 ms | 632 KB | Output is correct |
10 | Correct | 6 ms | 632 KB | Output is correct |
11 | Correct | 5 ms | 632 KB | Output is correct |
12 | Correct | 5 ms | 632 KB | Output is correct |
13 | Correct | 6 ms | 632 KB | Output is correct |
14 | Correct | 6 ms | 760 KB | Output is correct |
15 | Correct | 5 ms | 760 KB | Output is correct |
16 | Correct | 6 ms | 764 KB | Output is correct |
17 | Correct | 6 ms | 760 KB | Output is correct |
18 | Correct | 7 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 2348 KB | Output is correct |
2 | Correct | 21 ms | 1572 KB | Output is correct |
3 | Correct | 35 ms | 3180 KB | Output is correct |
4 | Correct | 34 ms | 2692 KB | Output is correct |
5 | Correct | 35 ms | 3168 KB | Output is correct |
6 | Correct | 42 ms | 3576 KB | Output is correct |
7 | Correct | 29 ms | 2352 KB | Output is correct |
8 | Correct | 44 ms | 3804 KB | Output is correct |
9 | Correct | 39 ms | 3440 KB | Output is correct |
10 | Correct | 41 ms | 3452 KB | Output is correct |
11 | Correct | 40 ms | 3444 KB | Output is correct |
12 | Correct | 41 ms | 3688 KB | Output is correct |
13 | Correct | 39 ms | 3428 KB | Output is correct |
14 | Correct | 40 ms | 3684 KB | Output is correct |
15 | Correct | 40 ms | 3784 KB | Output is correct |
16 | Correct | 40 ms | 3680 KB | Output is correct |
17 | Correct | 41 ms | 3708 KB | Output is correct |
18 | Correct | 41 ms | 3464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 65 ms | 6072 KB | Output is correct |
2 | Correct | 54 ms | 4352 KB | Output is correct |
3 | Correct | 75 ms | 6516 KB | Output is correct |
4 | Correct | 12 ms | 1188 KB | Output is correct |
5 | Correct | 85 ms | 7104 KB | Output is correct |
6 | Correct | 67 ms | 6192 KB | Output is correct |
7 | Correct | 77 ms | 6800 KB | Output is correct |
8 | Correct | 11 ms | 1088 KB | Output is correct |
9 | Correct | 83 ms | 7160 KB | Output is correct |
10 | Correct | 80 ms | 6568 KB | Output is correct |
11 | Correct | 77 ms | 6632 KB | Output is correct |
12 | Correct | 77 ms | 6636 KB | Output is correct |
13 | Correct | 84 ms | 7068 KB | Output is correct |
14 | Correct | 80 ms | 7128 KB | Output is correct |
15 | Correct | 79 ms | 7128 KB | Output is correct |
16 | Correct | 79 ms | 7112 KB | Output is correct |
17 | Correct | 80 ms | 7148 KB | Output is correct |
18 | Correct | 86 ms | 7128 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 116 ms | 8324 KB | Output is correct |
2 | Correct | 117 ms | 8368 KB | Output is correct |
3 | Correct | 103 ms | 7716 KB | Output is correct |
4 | Correct | 39 ms | 2684 KB | Output is correct |
5 | Correct | 127 ms | 8940 KB | Output is correct |
6 | Correct | 108 ms | 11476 KB | Output is correct |
7 | Correct | 93 ms | 10136 KB | Output is correct |
8 | Correct | 121 ms | 13008 KB | Output is correct |
9 | Correct | 153 ms | 18148 KB | Output is correct |
10 | Correct | 153 ms | 18128 KB | Output is correct |
11 | Correct | 152 ms | 18036 KB | Output is correct |
12 | Correct | 151 ms | 18144 KB | Output is correct |
13 | Correct | 153 ms | 18088 KB | Output is correct |
14 | Correct | 17 ms | 2168 KB | Output is correct |
15 | Correct | 169 ms | 19348 KB | Output is correct |
16 | Correct | 168 ms | 19320 KB | Output is correct |
17 | Correct | 168 ms | 19316 KB | Output is correct |
18 | Correct | 157 ms | 18064 KB | Output is correct |