# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
170786 | 2019-12-26T10:57:30 Z | gs18103 | Two Dishes (JOI19_dishes) | C++14 | 2287 ms | 151220 KB |
#include <cstdio> #include <algorithm> #include <map> #include <vector> int main() { int N, M; scanf("%d%d", &N, &M); std::vector<long long> A(N), B(M), S(N), T(M), P(N), Q(M); for(int i = 0; i < N; i++) { long long a, s, p; scanf("%lld%lld%lld", &a, &s, &p); A[i] = a; S[i] = s; P[i] = p; } for(int i = 0; i < M; i++) { long long b, t, q; scanf("%lld%lld%lld", &b, &t, &q); B[i] = b; T[i] = t; Q[i] = q; } long long ans = 0; std::vector<long long> asum(N); long long sum = 0; std::vector<std::pair<long long, std::pair<int, long long>>> margin; for(int i = 0; i < N; i++) { sum += A[i]; asum[i] = sum; if(sum <= S[i]) { ans += P[i]; margin.push_back(std::make_pair(S[i] - sum, std::make_pair(i, P[i]))); } } std::sort(margin.begin(), margin.end()); std::map<int, long long> mp; sum = 0; int pos = 0; for(int i = 0; i < M; i++) { sum += B[i]; std::vector<std::pair<int, long long>> v; while(pos < (int)margin.size() && margin[pos].first < sum) { v.push_back(margin[pos].second); pos++; } if(sum <= T[i]) { int p = std::upper_bound(asum.begin(), asum.end(), T[i] - sum) - asum.begin(); if(p < N) { v.push_back(std::make_pair(p, -Q[i])); } else { ans += Q[i]; } } std::sort(v.begin(), v.end()); for(int j = (int)v.size() - 1; j >= 0; j--) { if(v[j].second > 0) { mp[v[j].first] += v[j].second; } else if(v[j].second < 0) { auto it = mp.lower_bound(v[j].first); long long rem = -v[j].second; while(rem > 0 && it != mp.end()) { if(rem < it->second) { it->second -= rem; rem = 0; } else { rem -= it->second; it = mp.erase(it); } } ans += rem; } } } printf("%lld\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 261 ms | 26600 KB | Output is correct |
2 | Correct | 314 ms | 35164 KB | Output is correct |
3 | Correct | 227 ms | 28900 KB | Output is correct |
4 | Correct | 241 ms | 26980 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 271 ms | 28452 KB | Output is correct |
7 | Correct | 105 ms | 11860 KB | Output is correct |
8 | Correct | 124 ms | 19304 KB | Output is correct |
9 | Correct | 234 ms | 30844 KB | Output is correct |
10 | Correct | 214 ms | 24164 KB | Output is correct |
11 | Correct | 166 ms | 23500 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 | 376 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 256 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 | 256 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 | 256 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 256 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 | 256 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 5 ms | 760 KB | Output is correct |
18 | Correct | 4 ms | 504 KB | Output is correct |
19 | Correct | 5 ms | 632 KB | Output is correct |
20 | Correct | 4 ms | 504 KB | Output is correct |
21 | Correct | 4 ms | 636 KB | Output is correct |
22 | Correct | 4 ms | 632 KB | Output is correct |
23 | Correct | 4 ms | 508 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 | 376 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 256 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 | 256 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 5 ms | 760 KB | Output is correct |
18 | Correct | 4 ms | 504 KB | Output is correct |
19 | Correct | 5 ms | 632 KB | Output is correct |
20 | Correct | 4 ms | 504 KB | Output is correct |
21 | Correct | 4 ms | 636 KB | Output is correct |
22 | Correct | 4 ms | 632 KB | Output is correct |
23 | Correct | 4 ms | 508 KB | Output is correct |
24 | Correct | 319 ms | 41696 KB | Output is correct |
25 | Correct | 214 ms | 22380 KB | Output is correct |
26 | Correct | 299 ms | 38752 KB | Output is correct |
27 | Correct | 224 ms | 24940 KB | Output is correct |
28 | Correct | 255 ms | 26716 KB | Output is correct |
29 | Correct | 205 ms | 28904 KB | Output is correct |
30 | Correct | 348 ms | 26892 KB | Output is correct |
31 | Correct | 99 ms | 10232 KB | Output is correct |
32 | Correct | 163 ms | 24288 KB | Output is correct |
33 | Correct | 265 ms | 24812 KB | Output is correct |
34 | Correct | 363 ms | 30684 KB | Output is correct |
35 | Correct | 277 ms | 21860 KB | Output is correct |
36 | Correct | 279 ms | 21992 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 | 376 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 256 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 | 256 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 5 ms | 760 KB | Output is correct |
18 | Correct | 4 ms | 504 KB | Output is correct |
19 | Correct | 5 ms | 632 KB | Output is correct |
20 | Correct | 4 ms | 504 KB | Output is correct |
21 | Correct | 4 ms | 636 KB | Output is correct |
22 | Correct | 4 ms | 632 KB | Output is correct |
23 | Correct | 4 ms | 508 KB | Output is correct |
24 | Correct | 319 ms | 41696 KB | Output is correct |
25 | Correct | 214 ms | 22380 KB | Output is correct |
26 | Correct | 299 ms | 38752 KB | Output is correct |
27 | Correct | 224 ms | 24940 KB | Output is correct |
28 | Correct | 255 ms | 26716 KB | Output is correct |
29 | Correct | 205 ms | 28904 KB | Output is correct |
30 | Correct | 348 ms | 26892 KB | Output is correct |
31 | Correct | 99 ms | 10232 KB | Output is correct |
32 | Correct | 163 ms | 24288 KB | Output is correct |
33 | Correct | 265 ms | 24812 KB | Output is correct |
34 | Correct | 363 ms | 30684 KB | Output is correct |
35 | Correct | 277 ms | 21860 KB | Output is correct |
36 | Correct | 279 ms | 21992 KB | Output is correct |
37 | Correct | 328 ms | 38512 KB | Output is correct |
38 | Correct | 267 ms | 26348 KB | Output is correct |
39 | Correct | 242 ms | 25700 KB | Output is correct |
40 | Correct | 357 ms | 36188 KB | Output is correct |
41 | Correct | 2 ms | 376 KB | Output is correct |
42 | Correct | 412 ms | 24652 KB | Output is correct |
43 | Correct | 314 ms | 23148 KB | Output is correct |
44 | Correct | 382 ms | 29432 KB | Output is correct |
45 | Correct | 325 ms | 25064 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 | 376 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
6 | Correct | 2 ms | 256 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 | 256 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 376 KB | Output is correct |
17 | Correct | 5 ms | 760 KB | Output is correct |
18 | Correct | 4 ms | 504 KB | Output is correct |
19 | Correct | 5 ms | 632 KB | Output is correct |
20 | Correct | 4 ms | 504 KB | Output is correct |
21 | Correct | 4 ms | 636 KB | Output is correct |
22 | Correct | 4 ms | 632 KB | Output is correct |
23 | Correct | 4 ms | 508 KB | Output is correct |
24 | Correct | 319 ms | 41696 KB | Output is correct |
25 | Correct | 214 ms | 22380 KB | Output is correct |
26 | Correct | 299 ms | 38752 KB | Output is correct |
27 | Correct | 224 ms | 24940 KB | Output is correct |
28 | Correct | 255 ms | 26716 KB | Output is correct |
29 | Correct | 205 ms | 28904 KB | Output is correct |
30 | Correct | 348 ms | 26892 KB | Output is correct |
31 | Correct | 99 ms | 10232 KB | Output is correct |
32 | Correct | 163 ms | 24288 KB | Output is correct |
33 | Correct | 265 ms | 24812 KB | Output is correct |
34 | Correct | 363 ms | 30684 KB | Output is correct |
35 | Correct | 277 ms | 21860 KB | Output is correct |
36 | Correct | 279 ms | 21992 KB | Output is correct |
37 | Correct | 328 ms | 38512 KB | Output is correct |
38 | Correct | 267 ms | 26348 KB | Output is correct |
39 | Correct | 242 ms | 25700 KB | Output is correct |
40 | Correct | 357 ms | 36188 KB | Output is correct |
41 | Correct | 2 ms | 376 KB | Output is correct |
42 | Correct | 412 ms | 24652 KB | Output is correct |
43 | Correct | 314 ms | 23148 KB | Output is correct |
44 | Correct | 382 ms | 29432 KB | Output is correct |
45 | Correct | 325 ms | 25064 KB | Output is correct |
46 | Correct | 1716 ms | 151220 KB | Output is correct |
47 | Correct | 1389 ms | 69056 KB | Output is correct |
48 | Correct | 1195 ms | 89040 KB | Output is correct |
49 | Correct | 1949 ms | 142140 KB | Output is correct |
50 | Correct | 2287 ms | 87756 KB | Output is correct |
51 | Correct | 1606 ms | 68700 KB | Output is correct |
52 | Correct | 2033 ms | 99452 KB | Output is correct |
53 | Correct | 1801 ms | 82508 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 261 ms | 26600 KB | Output is correct |
2 | Correct | 314 ms | 35164 KB | Output is correct |
3 | Correct | 227 ms | 28900 KB | Output is correct |
4 | Correct | 241 ms | 26980 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 271 ms | 28452 KB | Output is correct |
7 | Correct | 105 ms | 11860 KB | Output is correct |
8 | Correct | 124 ms | 19304 KB | Output is correct |
9 | Correct | 234 ms | 30844 KB | Output is correct |
10 | Correct | 214 ms | 24164 KB | Output is correct |
11 | Correct | 166 ms | 23500 KB | Output is correct |
12 | Correct | 2 ms | 256 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 | 256 KB | Output is correct |
16 | Correct | 2 ms | 256 KB | Output is correct |
17 | Correct | 2 ms | 256 KB | Output is correct |
18 | Correct | 2 ms | 256 KB | Output is correct |
19 | Correct | 2 ms | 376 KB | Output is correct |
20 | Correct | 2 ms | 376 KB | Output is correct |
21 | Correct | 2 ms | 376 KB | Output is correct |
22 | Correct | 2 ms | 256 KB | Output is correct |
23 | Correct | 2 ms | 376 KB | Output is correct |
24 | Correct | 2 ms | 256 KB | Output is correct |
25 | Correct | 2 ms | 256 KB | Output is correct |
26 | Correct | 2 ms | 376 KB | Output is correct |
27 | Correct | 2 ms | 376 KB | Output is correct |
28 | Correct | 5 ms | 760 KB | Output is correct |
29 | Correct | 4 ms | 504 KB | Output is correct |
30 | Correct | 5 ms | 632 KB | Output is correct |
31 | Correct | 4 ms | 504 KB | Output is correct |
32 | Correct | 4 ms | 636 KB | Output is correct |
33 | Correct | 4 ms | 632 KB | Output is correct |
34 | Correct | 4 ms | 508 KB | Output is correct |
35 | Correct | 319 ms | 41696 KB | Output is correct |
36 | Correct | 214 ms | 22380 KB | Output is correct |
37 | Correct | 299 ms | 38752 KB | Output is correct |
38 | Correct | 224 ms | 24940 KB | Output is correct |
39 | Correct | 255 ms | 26716 KB | Output is correct |
40 | Correct | 205 ms | 28904 KB | Output is correct |
41 | Correct | 348 ms | 26892 KB | Output is correct |
42 | Correct | 99 ms | 10232 KB | Output is correct |
43 | Correct | 163 ms | 24288 KB | Output is correct |
44 | Correct | 265 ms | 24812 KB | Output is correct |
45 | Correct | 363 ms | 30684 KB | Output is correct |
46 | Correct | 277 ms | 21860 KB | Output is correct |
47 | Correct | 279 ms | 21992 KB | Output is correct |
48 | Correct | 328 ms | 38512 KB | Output is correct |
49 | Correct | 267 ms | 26348 KB | Output is correct |
50 | Correct | 242 ms | 25700 KB | Output is correct |
51 | Correct | 357 ms | 36188 KB | Output is correct |
52 | Correct | 2 ms | 376 KB | Output is correct |
53 | Correct | 412 ms | 24652 KB | Output is correct |
54 | Correct | 314 ms | 23148 KB | Output is correct |
55 | Correct | 382 ms | 29432 KB | Output is correct |
56 | Correct | 325 ms | 25064 KB | Output is correct |
57 | Correct | 254 ms | 22236 KB | Output is correct |
58 | Correct | 339 ms | 30876 KB | Output is correct |
59 | Correct | 375 ms | 30688 KB | Output is correct |
60 | Correct | 240 ms | 21352 KB | Output is correct |
61 | Correct | 286 ms | 22624 KB | Output is correct |
62 | Correct | 2 ms | 376 KB | Output is correct |
63 | Correct | 401 ms | 24552 KB | Output is correct |
64 | Correct | 314 ms | 20460 KB | Output is correct |
65 | Correct | 375 ms | 23688 KB | Output is correct |
66 | Correct | 326 ms | 22632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 261 ms | 26600 KB | Output is correct |
2 | Correct | 314 ms | 35164 KB | Output is correct |
3 | Correct | 227 ms | 28900 KB | Output is correct |
4 | Correct | 241 ms | 26980 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 271 ms | 28452 KB | Output is correct |
7 | Correct | 105 ms | 11860 KB | Output is correct |
8 | Correct | 124 ms | 19304 KB | Output is correct |
9 | Correct | 234 ms | 30844 KB | Output is correct |
10 | Correct | 214 ms | 24164 KB | Output is correct |
11 | Correct | 166 ms | 23500 KB | Output is correct |
12 | Correct | 2 ms | 256 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 | 256 KB | Output is correct |
16 | Correct | 2 ms | 256 KB | Output is correct |
17 | Correct | 2 ms | 256 KB | Output is correct |
18 | Correct | 2 ms | 256 KB | Output is correct |
19 | Correct | 2 ms | 376 KB | Output is correct |
20 | Correct | 2 ms | 376 KB | Output is correct |
21 | Correct | 2 ms | 376 KB | Output is correct |
22 | Correct | 2 ms | 256 KB | Output is correct |
23 | Correct | 2 ms | 376 KB | Output is correct |
24 | Correct | 2 ms | 256 KB | Output is correct |
25 | Correct | 2 ms | 256 KB | Output is correct |
26 | Correct | 2 ms | 376 KB | Output is correct |
27 | Correct | 2 ms | 376 KB | Output is correct |
28 | Correct | 5 ms | 760 KB | Output is correct |
29 | Correct | 4 ms | 504 KB | Output is correct |
30 | Correct | 5 ms | 632 KB | Output is correct |
31 | Correct | 4 ms | 504 KB | Output is correct |
32 | Correct | 4 ms | 636 KB | Output is correct |
33 | Correct | 4 ms | 632 KB | Output is correct |
34 | Correct | 4 ms | 508 KB | Output is correct |
35 | Correct | 319 ms | 41696 KB | Output is correct |
36 | Correct | 214 ms | 22380 KB | Output is correct |
37 | Correct | 299 ms | 38752 KB | Output is correct |
38 | Correct | 224 ms | 24940 KB | Output is correct |
39 | Correct | 255 ms | 26716 KB | Output is correct |
40 | Correct | 205 ms | 28904 KB | Output is correct |
41 | Correct | 348 ms | 26892 KB | Output is correct |
42 | Correct | 99 ms | 10232 KB | Output is correct |
43 | Correct | 163 ms | 24288 KB | Output is correct |
44 | Correct | 265 ms | 24812 KB | Output is correct |
45 | Correct | 363 ms | 30684 KB | Output is correct |
46 | Correct | 277 ms | 21860 KB | Output is correct |
47 | Correct | 279 ms | 21992 KB | Output is correct |
48 | Correct | 328 ms | 38512 KB | Output is correct |
49 | Correct | 267 ms | 26348 KB | Output is correct |
50 | Correct | 242 ms | 25700 KB | Output is correct |
51 | Correct | 357 ms | 36188 KB | Output is correct |
52 | Correct | 2 ms | 376 KB | Output is correct |
53 | Correct | 412 ms | 24652 KB | Output is correct |
54 | Correct | 314 ms | 23148 KB | Output is correct |
55 | Correct | 382 ms | 29432 KB | Output is correct |
56 | Correct | 325 ms | 25064 KB | Output is correct |
57 | Correct | 1716 ms | 151220 KB | Output is correct |
58 | Correct | 1389 ms | 69056 KB | Output is correct |
59 | Correct | 1195 ms | 89040 KB | Output is correct |
60 | Correct | 1949 ms | 142140 KB | Output is correct |
61 | Correct | 2287 ms | 87756 KB | Output is correct |
62 | Correct | 1606 ms | 68700 KB | Output is correct |
63 | Correct | 2033 ms | 99452 KB | Output is correct |
64 | Correct | 1801 ms | 82508 KB | Output is correct |
65 | Correct | 254 ms | 22236 KB | Output is correct |
66 | Correct | 339 ms | 30876 KB | Output is correct |
67 | Correct | 375 ms | 30688 KB | Output is correct |
68 | Correct | 240 ms | 21352 KB | Output is correct |
69 | Correct | 286 ms | 22624 KB | Output is correct |
70 | Correct | 2 ms | 376 KB | Output is correct |
71 | Correct | 401 ms | 24552 KB | Output is correct |
72 | Correct | 314 ms | 20460 KB | Output is correct |
73 | Correct | 375 ms | 23688 KB | Output is correct |
74 | Correct | 326 ms | 22632 KB | Output is correct |
75 | Correct | 1252 ms | 80500 KB | Output is correct |
76 | Correct | 1786 ms | 131452 KB | Output is correct |
77 | Correct | 2051 ms | 142788 KB | Output is correct |
78 | Correct | 1192 ms | 80204 KB | Output is correct |
79 | Correct | 2281 ms | 81740 KB | Output is correct |
80 | Correct | 1624 ms | 66336 KB | Output is correct |
81 | Correct | 2009 ms | 82908 KB | Output is correct |
82 | Correct | 1897 ms | 82380 KB | Output is correct |
83 | Correct | 2016 ms | 81356 KB | Output is correct |