# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
538832 |
2022-03-17T21:09:14 Z |
czhang2718 |
Cake 3 (JOI19_cake3) |
C++17 |
|
3638 ms |
14376 KB |
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=a; i<=b; i++)
typedef vector<int> vi;
#define pb push_back
#define f first
#define s second
typedef long long ll;
const int N=200000;
int n,M;
int V[N], C[N];
int ind[N];
ll ans=-1e18;
int cnt[4*N];
ll sum[4*N];
void upd(int i, int v, int x=0, int lx=0, int rx=n){
if(rx-lx==1){
cnt[x]=(v!=0);
sum[x]=v;
return;
}
int m=(lx+rx)/2;
if(i<m) upd(i, v, 2*x+1, lx, m);
else upd(i, v, 2*x+2, m, rx);
cnt[x]=cnt[2*x+1]+cnt[2*x+2];
sum[x]=sum[2*x+1]+sum[2*x+2];
}
ll walk(int k, int x=0, int lx=0, int rx=n){
if(k<=0) return 0;
if(rx-lx==1) return sum[x]; // why needed
int m=(lx+rx)/2;
if(cnt[2*x+2]<=k) return sum[2*x+2]+walk(k-cnt[2*x+2], 2*x+1, lx ,m);
return walk(k, 2*x+2, m, rx);
}
void solve(int l, int r, int a, int b){ // [l, r) [a, b]
if(r<=l || b<a) return;
int m=(l+r)/2;
// if(a>=m-(M-2)) return solve(m+1, r, a, b);
pair<ll, int> opt={-1e18, 0};
for(int i=m-1; i>=max(l, b+1); i--) upd(ind[i], V[i]);
for(int i=min(m-1, b); i>=a; i--){
if(m-i+1>=M) opt=max(opt, {walk(M-2)+V[m]+V[i]+2*C[i]-2*C[m], i});
upd(ind[i], V[i]);
}
ans=max(ans, opt.f);
// cout << "opt " << m << " " << opt.s << " " << opt.f << "\n";
for(int i=m-1; i>=max(l, b+1); i--) upd(ind[i], 0);
for(int i=min(m-1, b); i>=a; i--) upd(ind[i], 0);
for(int i=opt.s+1; i<=b; i++) if(i<l) upd(ind[i], V[i]);
solve(l, m, a, opt.s);
for(int i=opt.s+1; i<=b; i++) if(i<l) upd(ind[i], 0);
for(int i=max(b+1, l); i<=m; i++) upd(ind[i], V[i]);
solve(m+1, r, opt.s, b);
for(int i=max(b+1, l); i<=m; i++) upd(ind[i], 0);
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> M;
vector<pair<int, int>> vec;
rep(i,0,n-1){
int v,c; cin >> v >> c;
vec.push_back({c, v});
}
sort(vec.begin(), vec.end());
rep(i,0,n-1) V[i]=vec[i].second, C[i]=vec[i].first;
vec.clear();
rep(i,0,n-1) vec.push_back({V[i], i});
sort(vec.begin(), vec.end());
rep(i,0,n-1) ind[vec[i].s]=i;
solve(0, n, 0, n-1);
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
324 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 |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
324 KB |
Output is correct |
28 |
Correct |
1 ms |
324 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
324 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 |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
324 KB |
Output is correct |
28 |
Correct |
1 ms |
324 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
11 ms |
488 KB |
Output is correct |
39 |
Correct |
12 ms |
468 KB |
Output is correct |
40 |
Correct |
11 ms |
468 KB |
Output is correct |
41 |
Correct |
12 ms |
472 KB |
Output is correct |
42 |
Correct |
12 ms |
464 KB |
Output is correct |
43 |
Correct |
14 ms |
468 KB |
Output is correct |
44 |
Correct |
11 ms |
472 KB |
Output is correct |
45 |
Correct |
11 ms |
500 KB |
Output is correct |
46 |
Correct |
11 ms |
468 KB |
Output is correct |
47 |
Correct |
12 ms |
368 KB |
Output is correct |
48 |
Correct |
10 ms |
484 KB |
Output is correct |
49 |
Correct |
11 ms |
468 KB |
Output is correct |
50 |
Correct |
11 ms |
468 KB |
Output is correct |
51 |
Correct |
11 ms |
480 KB |
Output is correct |
52 |
Correct |
10 ms |
480 KB |
Output is correct |
53 |
Correct |
11 ms |
488 KB |
Output is correct |
54 |
Correct |
12 ms |
468 KB |
Output is correct |
55 |
Correct |
12 ms |
468 KB |
Output is correct |
56 |
Correct |
11 ms |
468 KB |
Output is correct |
57 |
Correct |
13 ms |
364 KB |
Output is correct |
58 |
Correct |
11 ms |
468 KB |
Output is correct |
59 |
Correct |
8 ms |
468 KB |
Output is correct |
60 |
Correct |
8 ms |
468 KB |
Output is correct |
61 |
Correct |
8 ms |
480 KB |
Output is correct |
62 |
Correct |
8 ms |
496 KB |
Output is correct |
63 |
Correct |
10 ms |
492 KB |
Output is correct |
64 |
Correct |
8 ms |
464 KB |
Output is correct |
65 |
Correct |
10 ms |
464 KB |
Output is correct |
66 |
Correct |
9 ms |
484 KB |
Output is correct |
67 |
Correct |
10 ms |
468 KB |
Output is correct |
68 |
Correct |
12 ms |
492 KB |
Output is correct |
69 |
Correct |
11 ms |
464 KB |
Output is correct |
70 |
Correct |
9 ms |
468 KB |
Output is correct |
71 |
Correct |
10 ms |
468 KB |
Output is correct |
72 |
Correct |
10 ms |
468 KB |
Output is correct |
73 |
Correct |
8 ms |
464 KB |
Output is correct |
74 |
Correct |
11 ms |
496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
324 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 |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
324 KB |
Output is correct |
28 |
Correct |
1 ms |
324 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
11 ms |
488 KB |
Output is correct |
39 |
Correct |
12 ms |
468 KB |
Output is correct |
40 |
Correct |
11 ms |
468 KB |
Output is correct |
41 |
Correct |
12 ms |
472 KB |
Output is correct |
42 |
Correct |
12 ms |
464 KB |
Output is correct |
43 |
Correct |
14 ms |
468 KB |
Output is correct |
44 |
Correct |
11 ms |
472 KB |
Output is correct |
45 |
Correct |
11 ms |
500 KB |
Output is correct |
46 |
Correct |
11 ms |
468 KB |
Output is correct |
47 |
Correct |
12 ms |
368 KB |
Output is correct |
48 |
Correct |
10 ms |
484 KB |
Output is correct |
49 |
Correct |
11 ms |
468 KB |
Output is correct |
50 |
Correct |
11 ms |
468 KB |
Output is correct |
51 |
Correct |
11 ms |
480 KB |
Output is correct |
52 |
Correct |
10 ms |
480 KB |
Output is correct |
53 |
Correct |
11 ms |
488 KB |
Output is correct |
54 |
Correct |
12 ms |
468 KB |
Output is correct |
55 |
Correct |
12 ms |
468 KB |
Output is correct |
56 |
Correct |
11 ms |
468 KB |
Output is correct |
57 |
Correct |
13 ms |
364 KB |
Output is correct |
58 |
Correct |
11 ms |
468 KB |
Output is correct |
59 |
Correct |
8 ms |
468 KB |
Output is correct |
60 |
Correct |
8 ms |
468 KB |
Output is correct |
61 |
Correct |
8 ms |
480 KB |
Output is correct |
62 |
Correct |
8 ms |
496 KB |
Output is correct |
63 |
Correct |
10 ms |
492 KB |
Output is correct |
64 |
Correct |
8 ms |
464 KB |
Output is correct |
65 |
Correct |
10 ms |
464 KB |
Output is correct |
66 |
Correct |
9 ms |
484 KB |
Output is correct |
67 |
Correct |
10 ms |
468 KB |
Output is correct |
68 |
Correct |
12 ms |
492 KB |
Output is correct |
69 |
Correct |
11 ms |
464 KB |
Output is correct |
70 |
Correct |
9 ms |
468 KB |
Output is correct |
71 |
Correct |
10 ms |
468 KB |
Output is correct |
72 |
Correct |
10 ms |
468 KB |
Output is correct |
73 |
Correct |
8 ms |
464 KB |
Output is correct |
74 |
Correct |
11 ms |
496 KB |
Output is correct |
75 |
Correct |
3638 ms |
13848 KB |
Output is correct |
76 |
Correct |
3478 ms |
13572 KB |
Output is correct |
77 |
Correct |
3555 ms |
13788 KB |
Output is correct |
78 |
Correct |
3402 ms |
13972 KB |
Output is correct |
79 |
Correct |
3247 ms |
14032 KB |
Output is correct |
80 |
Correct |
3178 ms |
13804 KB |
Output is correct |
81 |
Correct |
2960 ms |
13120 KB |
Output is correct |
82 |
Correct |
2983 ms |
13248 KB |
Output is correct |
83 |
Correct |
3087 ms |
13404 KB |
Output is correct |
84 |
Correct |
3171 ms |
13516 KB |
Output is correct |
85 |
Correct |
3116 ms |
13120 KB |
Output is correct |
86 |
Correct |
2997 ms |
12876 KB |
Output is correct |
87 |
Correct |
2882 ms |
12812 KB |
Output is correct |
88 |
Correct |
2801 ms |
12760 KB |
Output is correct |
89 |
Correct |
3087 ms |
13204 KB |
Output is correct |
90 |
Correct |
3163 ms |
13436 KB |
Output is correct |
91 |
Correct |
2913 ms |
12928 KB |
Output is correct |
92 |
Correct |
2943 ms |
12864 KB |
Output is correct |
93 |
Correct |
3009 ms |
13124 KB |
Output is correct |
94 |
Correct |
3272 ms |
13376 KB |
Output is correct |
95 |
Correct |
3211 ms |
13516 KB |
Output is correct |
96 |
Correct |
1689 ms |
12996 KB |
Output is correct |
97 |
Correct |
1835 ms |
13460 KB |
Output is correct |
98 |
Correct |
1760 ms |
13292 KB |
Output is correct |
99 |
Correct |
1780 ms |
13432 KB |
Output is correct |
100 |
Correct |
1719 ms |
13048 KB |
Output is correct |
101 |
Correct |
1712 ms |
13060 KB |
Output is correct |
102 |
Correct |
2277 ms |
12976 KB |
Output is correct |
103 |
Correct |
2176 ms |
12928 KB |
Output is correct |
104 |
Correct |
2230 ms |
13264 KB |
Output is correct |
105 |
Correct |
2413 ms |
13272 KB |
Output is correct |
106 |
Correct |
2466 ms |
13504 KB |
Output is correct |
107 |
Correct |
2420 ms |
13088 KB |
Output is correct |
108 |
Correct |
3286 ms |
13780 KB |
Output is correct |
109 |
Correct |
3554 ms |
14092 KB |
Output is correct |
110 |
Correct |
2148 ms |
12460 KB |
Output is correct |
111 |
Correct |
2087 ms |
12556 KB |
Output is correct |
112 |
Correct |
1615 ms |
12196 KB |
Output is correct |
113 |
Correct |
3483 ms |
14376 KB |
Output is correct |