# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
130878 | 2019-07-16T08:01:21 Z | 임유진(#3171) | Bodyguards (CEOI10_bodyguards) | C++14 | 115 ms | 8420 KB |
#include <stdio.h> #include <vector> #include <algorithm> 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; } cv.push_back(make_pair(0ll, 1ll << 30)); sort(rv.begin(), rv.end()); sort(cv.begin(), cv.end()); 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(auto a : rv) { //printf("cv : "); //for(auto a : cv) printf("(%lld, %lld)", a.fi, a.se); //printf("\n"); if(cv[cv.size() - 2].se < a.fi || (cv.back().fi > cv[cv.size() - 2].fi + 1 && cv.back().se < a.fi)) { printf("0"); return 0; } lint left = a.fi * a.se; //printf("a = (%lld, %lld), left = %lld\n", a.fi, a.se, left); while(left > 0) { if(left >= cv.back().se * (cv.back().fi - cv[cv.size() - 2].fi)) { cv[cv.size() - 2].se += cv.back().se; left -= cv.back().se * (cv.back().fi - cv[cv.size() - 2].fi); cv.pop_back(); } else { pll p = cv.back(); cv.back().fi -= (left - 1) / p.se + 1; cv.back().se = (left - 1) % p.se + 1; if(cv.back().fi == cv[cv.size() - 2].fi) { cv[cv.size() - 2].se += cv.back().se; cv.pop_back(); } if(left % p.se) cv.push_back(make_pair(cv.back().fi + 1, p.se - left % p.se)); left = 0; } } } printf("1"); return 0; }
Compilation message
# | 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 | 256 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Incorrect | 2 ms | 376 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 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 | Incorrect | 2 ms | 376 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 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 | 376 KB | Output is correct |
4 | Incorrect | 2 ms | 376 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Incorrect | 2 ms | 376 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 256 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 632 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 2308 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 62 ms | 6000 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 115 ms | 8420 KB | Output is correct |
2 | Correct | 113 ms | 8352 KB | Output is correct |
3 | Correct | 100 ms | 7484 KB | Output is correct |
4 | Incorrect | 39 ms | 2808 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |