# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
585870 |
2022-06-29T13:11:14 Z |
Lucpp |
Two Dishes (JOI19_dishes) |
C++17 |
|
2224 ms |
193040 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 1e6+2;
ll A[2][MAX], T[2][MAX], P[2][MAX];
int n[2], B[2][MAX];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n[0] >> n[1];
for(int i = 0; i < 2; i++){
A[i][0] = 0;
for(int j = 1; j <= n[i]; j++){
cin >> A[i][j] >> T[i][j] >> P[i][j-1];
A[i][j] += A[i][j-1];
}
}
for(int i = 0; i < 2; i++){
for(int j = 1; j <= n[i]; j++){
if(A[i][j] > T[i][j]) B[i][j-1] = -1;
else if(A[i][j]+A[1-i][n[1-i]] <= T[i][j]) B[i][j-1] = n[1-i];
else B[i][j-1] = (int)(upper_bound(A[1-i], A[1-i]+n[1-i], T[i][j]-A[i][j])-A[1-i]-1);
// cerr << B[i][j-1] << " ";
}
// cerr << "\n";
}
vector<vector<int>> todo(n[0]+2);
ll sum = 0;
for(int i = 0; i < n[1]; i++){
if(B[1][i] > -1) todo[B[1][i]].push_back(i), sum += P[1][i];
}
map<int, ll> s;
set<int> toCorrect;
s.emplace(0, sum);
auto correct = [&](int i){
auto it = s.find(i);
if(it == s.end() || it->second >= 0) return;
ll x = it->second;
while(true){
it = s.erase(it);
if(it == s.end()) break;
it->second += x;
if(it->second >= 0) break;
x = it->second;
}
};
auto upd = [&](int i, ll v){
s[0] += v;
s[i+1] += -v;
toCorrect.insert(0);
toCorrect.insert(i+1);
};
for(int i = 0; i < n[0]; i++){
toCorrect.clear();
if(B[0][i] > -1) upd(B[0][i], P[0][i]);
for(int j : todo[i]){
upd(j, -P[1][j]);
}
for(int j : toCorrect) correct(j);
// cerr << i << ":\n";
// for(auto [j, x] : s){
// cerr << " " << j << " " << x << "\n";
// }
}
ll ans = 0;
for(auto [i, x] : s) ans += x;
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
251 ms |
44260 KB |
Output is correct |
2 |
Correct |
203 ms |
33184 KB |
Output is correct |
3 |
Correct |
165 ms |
30448 KB |
Output is correct |
4 |
Correct |
212 ms |
40696 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
206 ms |
32116 KB |
Output is correct |
7 |
Correct |
73 ms |
13740 KB |
Output is correct |
8 |
Correct |
94 ms |
17520 KB |
Output is correct |
9 |
Correct |
170 ms |
31524 KB |
Output is correct |
10 |
Correct |
177 ms |
29792 KB |
Output is correct |
11 |
Correct |
115 ms |
24892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
328 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
328 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
3 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
3 ms |
724 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
328 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
3 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
3 ms |
724 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
24 |
Correct |
159 ms |
27180 KB |
Output is correct |
25 |
Correct |
313 ms |
49272 KB |
Output is correct |
26 |
Correct |
149 ms |
27292 KB |
Output is correct |
27 |
Correct |
263 ms |
45380 KB |
Output is correct |
28 |
Correct |
193 ms |
28704 KB |
Output is correct |
29 |
Correct |
144 ms |
28476 KB |
Output is correct |
30 |
Correct |
307 ms |
30876 KB |
Output is correct |
31 |
Correct |
111 ms |
22828 KB |
Output is correct |
32 |
Correct |
82 ms |
15692 KB |
Output is correct |
33 |
Correct |
210 ms |
28732 KB |
Output is correct |
34 |
Correct |
327 ms |
34352 KB |
Output is correct |
35 |
Correct |
274 ms |
24316 KB |
Output is correct |
36 |
Correct |
269 ms |
24492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
328 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
3 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
3 ms |
724 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
24 |
Correct |
159 ms |
27180 KB |
Output is correct |
25 |
Correct |
313 ms |
49272 KB |
Output is correct |
26 |
Correct |
149 ms |
27292 KB |
Output is correct |
27 |
Correct |
263 ms |
45380 KB |
Output is correct |
28 |
Correct |
193 ms |
28704 KB |
Output is correct |
29 |
Correct |
144 ms |
28476 KB |
Output is correct |
30 |
Correct |
307 ms |
30876 KB |
Output is correct |
31 |
Correct |
111 ms |
22828 KB |
Output is correct |
32 |
Correct |
82 ms |
15692 KB |
Output is correct |
33 |
Correct |
210 ms |
28732 KB |
Output is correct |
34 |
Correct |
327 ms |
34352 KB |
Output is correct |
35 |
Correct |
274 ms |
24316 KB |
Output is correct |
36 |
Correct |
269 ms |
24492 KB |
Output is correct |
37 |
Correct |
186 ms |
30272 KB |
Output is correct |
38 |
Correct |
307 ms |
48452 KB |
Output is correct |
39 |
Correct |
326 ms |
45772 KB |
Output is correct |
40 |
Correct |
173 ms |
33324 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
366 ms |
33844 KB |
Output is correct |
43 |
Correct |
254 ms |
31564 KB |
Output is correct |
44 |
Correct |
327 ms |
37328 KB |
Output is correct |
45 |
Correct |
298 ms |
27440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
328 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
2 ms |
596 KB |
Output is correct |
18 |
Correct |
3 ms |
852 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
3 ms |
724 KB |
Output is correct |
22 |
Correct |
3 ms |
596 KB |
Output is correct |
23 |
Correct |
2 ms |
596 KB |
Output is correct |
24 |
Correct |
159 ms |
27180 KB |
Output is correct |
25 |
Correct |
313 ms |
49272 KB |
Output is correct |
26 |
Correct |
149 ms |
27292 KB |
Output is correct |
27 |
Correct |
263 ms |
45380 KB |
Output is correct |
28 |
Correct |
193 ms |
28704 KB |
Output is correct |
29 |
Correct |
144 ms |
28476 KB |
Output is correct |
30 |
Correct |
307 ms |
30876 KB |
Output is correct |
31 |
Correct |
111 ms |
22828 KB |
Output is correct |
32 |
Correct |
82 ms |
15692 KB |
Output is correct |
33 |
Correct |
210 ms |
28732 KB |
Output is correct |
34 |
Correct |
327 ms |
34352 KB |
Output is correct |
35 |
Correct |
274 ms |
24316 KB |
Output is correct |
36 |
Correct |
269 ms |
24492 KB |
Output is correct |
37 |
Correct |
186 ms |
30272 KB |
Output is correct |
38 |
Correct |
307 ms |
48452 KB |
Output is correct |
39 |
Correct |
326 ms |
45772 KB |
Output is correct |
40 |
Correct |
173 ms |
33324 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
366 ms |
33844 KB |
Output is correct |
43 |
Correct |
254 ms |
31564 KB |
Output is correct |
44 |
Correct |
327 ms |
37328 KB |
Output is correct |
45 |
Correct |
298 ms |
27440 KB |
Output is correct |
46 |
Correct |
916 ms |
101240 KB |
Output is correct |
47 |
Correct |
1604 ms |
193040 KB |
Output is correct |
48 |
Correct |
1842 ms |
188064 KB |
Output is correct |
49 |
Correct |
895 ms |
125220 KB |
Output is correct |
50 |
Correct |
2224 ms |
119180 KB |
Output is correct |
51 |
Correct |
1393 ms |
106380 KB |
Output is correct |
52 |
Correct |
2037 ms |
133200 KB |
Output is correct |
53 |
Correct |
1807 ms |
107820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
251 ms |
44260 KB |
Output is correct |
2 |
Correct |
203 ms |
33184 KB |
Output is correct |
3 |
Correct |
165 ms |
30448 KB |
Output is correct |
4 |
Correct |
212 ms |
40696 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
206 ms |
32116 KB |
Output is correct |
7 |
Correct |
73 ms |
13740 KB |
Output is correct |
8 |
Correct |
94 ms |
17520 KB |
Output is correct |
9 |
Correct |
170 ms |
31524 KB |
Output is correct |
10 |
Correct |
177 ms |
29792 KB |
Output is correct |
11 |
Correct |
115 ms |
24892 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
324 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
328 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
596 KB |
Output is correct |
29 |
Correct |
3 ms |
852 KB |
Output is correct |
30 |
Correct |
3 ms |
596 KB |
Output is correct |
31 |
Correct |
3 ms |
596 KB |
Output is correct |
32 |
Correct |
3 ms |
724 KB |
Output is correct |
33 |
Correct |
3 ms |
596 KB |
Output is correct |
34 |
Correct |
2 ms |
596 KB |
Output is correct |
35 |
Correct |
159 ms |
27180 KB |
Output is correct |
36 |
Correct |
313 ms |
49272 KB |
Output is correct |
37 |
Correct |
149 ms |
27292 KB |
Output is correct |
38 |
Correct |
263 ms |
45380 KB |
Output is correct |
39 |
Correct |
193 ms |
28704 KB |
Output is correct |
40 |
Correct |
144 ms |
28476 KB |
Output is correct |
41 |
Correct |
307 ms |
30876 KB |
Output is correct |
42 |
Correct |
111 ms |
22828 KB |
Output is correct |
43 |
Correct |
82 ms |
15692 KB |
Output is correct |
44 |
Correct |
210 ms |
28732 KB |
Output is correct |
45 |
Correct |
327 ms |
34352 KB |
Output is correct |
46 |
Correct |
274 ms |
24316 KB |
Output is correct |
47 |
Correct |
269 ms |
24492 KB |
Output is correct |
48 |
Correct |
186 ms |
30272 KB |
Output is correct |
49 |
Correct |
307 ms |
48452 KB |
Output is correct |
50 |
Correct |
326 ms |
45772 KB |
Output is correct |
51 |
Correct |
173 ms |
33324 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Correct |
366 ms |
33844 KB |
Output is correct |
54 |
Correct |
254 ms |
31564 KB |
Output is correct |
55 |
Correct |
327 ms |
37328 KB |
Output is correct |
56 |
Correct |
298 ms |
27440 KB |
Output is correct |
57 |
Incorrect |
204 ms |
30800 KB |
Output isn't correct |
58 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
251 ms |
44260 KB |
Output is correct |
2 |
Correct |
203 ms |
33184 KB |
Output is correct |
3 |
Correct |
165 ms |
30448 KB |
Output is correct |
4 |
Correct |
212 ms |
40696 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
206 ms |
32116 KB |
Output is correct |
7 |
Correct |
73 ms |
13740 KB |
Output is correct |
8 |
Correct |
94 ms |
17520 KB |
Output is correct |
9 |
Correct |
170 ms |
31524 KB |
Output is correct |
10 |
Correct |
177 ms |
29792 KB |
Output is correct |
11 |
Correct |
115 ms |
24892 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
324 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
328 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
596 KB |
Output is correct |
29 |
Correct |
3 ms |
852 KB |
Output is correct |
30 |
Correct |
3 ms |
596 KB |
Output is correct |
31 |
Correct |
3 ms |
596 KB |
Output is correct |
32 |
Correct |
3 ms |
724 KB |
Output is correct |
33 |
Correct |
3 ms |
596 KB |
Output is correct |
34 |
Correct |
2 ms |
596 KB |
Output is correct |
35 |
Correct |
159 ms |
27180 KB |
Output is correct |
36 |
Correct |
313 ms |
49272 KB |
Output is correct |
37 |
Correct |
149 ms |
27292 KB |
Output is correct |
38 |
Correct |
263 ms |
45380 KB |
Output is correct |
39 |
Correct |
193 ms |
28704 KB |
Output is correct |
40 |
Correct |
144 ms |
28476 KB |
Output is correct |
41 |
Correct |
307 ms |
30876 KB |
Output is correct |
42 |
Correct |
111 ms |
22828 KB |
Output is correct |
43 |
Correct |
82 ms |
15692 KB |
Output is correct |
44 |
Correct |
210 ms |
28732 KB |
Output is correct |
45 |
Correct |
327 ms |
34352 KB |
Output is correct |
46 |
Correct |
274 ms |
24316 KB |
Output is correct |
47 |
Correct |
269 ms |
24492 KB |
Output is correct |
48 |
Correct |
186 ms |
30272 KB |
Output is correct |
49 |
Correct |
307 ms |
48452 KB |
Output is correct |
50 |
Correct |
326 ms |
45772 KB |
Output is correct |
51 |
Correct |
173 ms |
33324 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Correct |
366 ms |
33844 KB |
Output is correct |
54 |
Correct |
254 ms |
31564 KB |
Output is correct |
55 |
Correct |
327 ms |
37328 KB |
Output is correct |
56 |
Correct |
298 ms |
27440 KB |
Output is correct |
57 |
Correct |
916 ms |
101240 KB |
Output is correct |
58 |
Correct |
1604 ms |
193040 KB |
Output is correct |
59 |
Correct |
1842 ms |
188064 KB |
Output is correct |
60 |
Correct |
895 ms |
125220 KB |
Output is correct |
61 |
Correct |
2224 ms |
119180 KB |
Output is correct |
62 |
Correct |
1393 ms |
106380 KB |
Output is correct |
63 |
Correct |
2037 ms |
133200 KB |
Output is correct |
64 |
Correct |
1807 ms |
107820 KB |
Output is correct |
65 |
Incorrect |
204 ms |
30800 KB |
Output isn't correct |
66 |
Halted |
0 ms |
0 KB |
- |