#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <set>
#include <stdint.h>
#include <map>
const int64_t INF=1e15+7;
std::vector<std::pair<int,int> > cake;
int cps[200005];
int N,M;
const int MAXN=1<<18;
struct Node{
int cnt;
int64_t sum;
Node():cnt(0),sum(0){
}
}st[MAXN*2];
void st_add(int i,int c,int64_t v){
//printf("st_add(%d,%d,%ld)\n",i,c,v);
for(i+=MAXN;i>0;i>>=1){
st[i].cnt+=c;
st[i].sum+=v;
}
}
/*
void st_insert(int x,int c){
//printf("st_insert(%d) x%d\n",x,c);
assert(cps[x]>=0&&cps[x]<MAXN);
st_add(cps[x],c,x*c);
}
*/
int64_t st_sum(int w,int L,int R,int k){
assert(st[w].cnt>=k);
if(k==0) return 0;
if(st[w].cnt==k){
return st[w].sum;
}
int M=(L+R)/2;
if(st[w<<1|1].cnt>=k){
return st_sum(w<<1|1,M,R,k);
}else{
return st_sum(w<<1,L,M,k-st[w<<1|1].cnt)+st[w<<1|1].sum;
}
}
void st_dump();
int64_t st_sum(int k){
/*
int64_t sum=0,cnt=0;
for(int i=MAXN-1;i>=0&&cnt<k;i--){
sum+=st[i+MAXN].sum;
cnt+=st[i+MAXN].cnt;
}
assert(cnt==k);
*/
//st_dump();
//printf("st_sum(%d)=%ld\n",k,sum);
//return sum;
//assert(sum==st_sum(1,0,MAXN,k));
return st_sum(1,0,MAXN,k);
}
void st_dump(){
for(int i=0;i<2*MAXN;i++){
if(st[i].cnt) printf(" ST[%d](%d): %ld\n",i,st[i].cnt,st[i].sum);
}
}
struct DataStruct{
int ll,rr;//(ll,rr) for elements, [ll,rr] for query
DataStruct():ll(0),rr(1){
}
void add(int i){
st_add(cps[i],1,cake[i].second);
}
void rem(int i){
st_add(cps[i],-1,-cake[i].second);
}
int64_t query(int l,int r){
if(r-l+1<M) return -INF;
while(ll>l) add(ll--);
while(rr<r) add(rr++);
while(ll<l) rem(++ll);
while(rr>r) rem(--rr);
return st_sum(M-2)+cake[l].second+cake[r].second+2LL*(cake[l].first-cake[r].first);
}
}ds;
int64_t best=-INF;
//find ans for (l,r), which must be in range [low,high]
void solve(int l,int r,int low,int high){
if(r-l<=1) return;
int m=(l+r)/2;
int64_t max=-INF;
int maxi=-1;
for(int i=low;i<=high;i++){
int64_t res=ds.query(m,i);
if(res>=max){
maxi=i;
max=res;
}
}
best=std::max(best,max);
//printf("best with l=%ld: %ld\n",m,max);
solve(l,m,low,maxi);
solve(m,r,maxi,high);
}
int64_t brute(int64_t l,int64_t r){
if(r-l+1<M) return -INF;
std::multiset<int> best;
for(int64_t i=l+1;i<r;i++){
best.insert(cake[i].second);
}
while(best.size()>M-2){
best.erase(best.begin());
}
assert(best.size()==M-2);
best.insert(cake[l].second);
best.insert(cake[r].second);
int64_t sum=2LL*(cake[l].first-cake[r].first);
for(int64_t x:best){
sum+=x;
}
return sum;
}
int main(){
scanf("%d %d",&N,&M);
std::vector<std::pair<int,int> > vs;
for(int i=0;i<N;i++){
int V,C;
scanf("%d %d",&V,&C);
cake.push_back({C,V});
}
std::sort(cake.begin(),cake.end());
for(int i=0;i<N;i++){
vs.push_back({cake[i].second,i});
}
std::sort(vs.begin(),vs.end());
for(int i=0;i<N;i++){
cps[vs[i].second]=i;
}
/*
for(int l=0;l<N;l++){
for(int r=0;r<N;r++){
printf("%ld,%ld ",ds.query(l,r),brute(l,r));
//assert(ds.query(l,r)==brute(l,r));
}
printf("\n");
}
*/
solve(-1,N,0,N-1);
/*
for(int l=0;l<N;l++){
for(int r=l;r<N;r++){
best=std::max(best,brute(l,r));
}
}
*/
printf("%ld\n",best);
//ds.query(0,N-1),ds.dump();
return 0;
}
Compilation message
cake3.cpp: In function 'int64_t brute(int64_t, int64_t)':
cake3.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(best.size()>M-2){
~~~~~~~~~~~^~~~
In file included from /usr/include/c++/7/cassert:44:0,
from cake3.cpp:5:
cake3.cpp:130:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(best.size()==M-2);
~~~~~~~~~~~^~~~~
cake3.cpp: In function 'int main()':
cake3.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&M);
~~~~~^~~~~~~~~~~~~~~
cake3.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&V,&C);
~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8448 KB |
Output is correct |
2 |
Correct |
10 ms |
8576 KB |
Output is correct |
3 |
Correct |
10 ms |
8576 KB |
Output is correct |
4 |
Correct |
9 ms |
8576 KB |
Output is correct |
5 |
Correct |
8 ms |
8448 KB |
Output is correct |
6 |
Correct |
10 ms |
8576 KB |
Output is correct |
7 |
Correct |
8 ms |
8576 KB |
Output is correct |
8 |
Correct |
10 ms |
8576 KB |
Output is correct |
9 |
Correct |
9 ms |
8576 KB |
Output is correct |
10 |
Correct |
10 ms |
8576 KB |
Output is correct |
11 |
Correct |
8 ms |
8576 KB |
Output is correct |
12 |
Correct |
8 ms |
8576 KB |
Output is correct |
13 |
Correct |
8 ms |
8576 KB |
Output is correct |
14 |
Correct |
9 ms |
8576 KB |
Output is correct |
15 |
Correct |
9 ms |
8576 KB |
Output is correct |
16 |
Correct |
10 ms |
8576 KB |
Output is correct |
17 |
Correct |
9 ms |
8576 KB |
Output is correct |
18 |
Correct |
9 ms |
8448 KB |
Output is correct |
19 |
Correct |
9 ms |
8576 KB |
Output is correct |
20 |
Correct |
8 ms |
8448 KB |
Output is correct |
21 |
Correct |
8 ms |
8448 KB |
Output is correct |
22 |
Correct |
10 ms |
8576 KB |
Output is correct |
23 |
Correct |
9 ms |
8448 KB |
Output is correct |
24 |
Correct |
10 ms |
8576 KB |
Output is correct |
25 |
Correct |
10 ms |
8448 KB |
Output is correct |
26 |
Correct |
9 ms |
8576 KB |
Output is correct |
27 |
Correct |
12 ms |
8576 KB |
Output is correct |
28 |
Correct |
8 ms |
8576 KB |
Output is correct |
29 |
Correct |
9 ms |
8576 KB |
Output is correct |
30 |
Correct |
9 ms |
8576 KB |
Output is correct |
31 |
Correct |
9 ms |
8576 KB |
Output is correct |
32 |
Correct |
9 ms |
8448 KB |
Output is correct |
33 |
Correct |
8 ms |
8576 KB |
Output is correct |
34 |
Correct |
10 ms |
8576 KB |
Output is correct |
35 |
Correct |
8 ms |
8576 KB |
Output is correct |
36 |
Correct |
9 ms |
8576 KB |
Output is correct |
37 |
Correct |
8 ms |
8576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8448 KB |
Output is correct |
2 |
Correct |
10 ms |
8576 KB |
Output is correct |
3 |
Correct |
10 ms |
8576 KB |
Output is correct |
4 |
Correct |
9 ms |
8576 KB |
Output is correct |
5 |
Correct |
8 ms |
8448 KB |
Output is correct |
6 |
Correct |
10 ms |
8576 KB |
Output is correct |
7 |
Correct |
8 ms |
8576 KB |
Output is correct |
8 |
Correct |
10 ms |
8576 KB |
Output is correct |
9 |
Correct |
9 ms |
8576 KB |
Output is correct |
10 |
Correct |
10 ms |
8576 KB |
Output is correct |
11 |
Correct |
8 ms |
8576 KB |
Output is correct |
12 |
Correct |
8 ms |
8576 KB |
Output is correct |
13 |
Correct |
8 ms |
8576 KB |
Output is correct |
14 |
Correct |
9 ms |
8576 KB |
Output is correct |
15 |
Correct |
9 ms |
8576 KB |
Output is correct |
16 |
Correct |
10 ms |
8576 KB |
Output is correct |
17 |
Correct |
9 ms |
8576 KB |
Output is correct |
18 |
Correct |
9 ms |
8448 KB |
Output is correct |
19 |
Correct |
9 ms |
8576 KB |
Output is correct |
20 |
Correct |
8 ms |
8448 KB |
Output is correct |
21 |
Correct |
8 ms |
8448 KB |
Output is correct |
22 |
Correct |
10 ms |
8576 KB |
Output is correct |
23 |
Correct |
9 ms |
8448 KB |
Output is correct |
24 |
Correct |
10 ms |
8576 KB |
Output is correct |
25 |
Correct |
10 ms |
8448 KB |
Output is correct |
26 |
Correct |
9 ms |
8576 KB |
Output is correct |
27 |
Correct |
12 ms |
8576 KB |
Output is correct |
28 |
Correct |
8 ms |
8576 KB |
Output is correct |
29 |
Correct |
9 ms |
8576 KB |
Output is correct |
30 |
Correct |
9 ms |
8576 KB |
Output is correct |
31 |
Correct |
9 ms |
8576 KB |
Output is correct |
32 |
Correct |
9 ms |
8448 KB |
Output is correct |
33 |
Correct |
8 ms |
8576 KB |
Output is correct |
34 |
Correct |
10 ms |
8576 KB |
Output is correct |
35 |
Correct |
8 ms |
8576 KB |
Output is correct |
36 |
Correct |
9 ms |
8576 KB |
Output is correct |
37 |
Correct |
8 ms |
8576 KB |
Output is correct |
38 |
Correct |
10 ms |
8576 KB |
Output is correct |
39 |
Correct |
10 ms |
8576 KB |
Output is correct |
40 |
Correct |
11 ms |
8576 KB |
Output is correct |
41 |
Correct |
11 ms |
8576 KB |
Output is correct |
42 |
Correct |
11 ms |
8576 KB |
Output is correct |
43 |
Correct |
12 ms |
8704 KB |
Output is correct |
44 |
Correct |
13 ms |
8576 KB |
Output is correct |
45 |
Correct |
13 ms |
8576 KB |
Output is correct |
46 |
Correct |
12 ms |
8576 KB |
Output is correct |
47 |
Correct |
12 ms |
8576 KB |
Output is correct |
48 |
Correct |
12 ms |
8576 KB |
Output is correct |
49 |
Correct |
12 ms |
8576 KB |
Output is correct |
50 |
Correct |
11 ms |
8576 KB |
Output is correct |
51 |
Correct |
10 ms |
8704 KB |
Output is correct |
52 |
Correct |
11 ms |
8576 KB |
Output is correct |
53 |
Correct |
10 ms |
8576 KB |
Output is correct |
54 |
Correct |
14 ms |
8652 KB |
Output is correct |
55 |
Correct |
11 ms |
8548 KB |
Output is correct |
56 |
Correct |
9 ms |
8576 KB |
Output is correct |
57 |
Correct |
10 ms |
8576 KB |
Output is correct |
58 |
Correct |
11 ms |
8576 KB |
Output is correct |
59 |
Correct |
12 ms |
8576 KB |
Output is correct |
60 |
Correct |
13 ms |
8576 KB |
Output is correct |
61 |
Correct |
10 ms |
8576 KB |
Output is correct |
62 |
Correct |
13 ms |
8576 KB |
Output is correct |
63 |
Correct |
10 ms |
8576 KB |
Output is correct |
64 |
Correct |
10 ms |
8576 KB |
Output is correct |
65 |
Correct |
13 ms |
8704 KB |
Output is correct |
66 |
Correct |
12 ms |
8576 KB |
Output is correct |
67 |
Correct |
11 ms |
8576 KB |
Output is correct |
68 |
Correct |
10 ms |
8576 KB |
Output is correct |
69 |
Correct |
9 ms |
8576 KB |
Output is correct |
70 |
Correct |
10 ms |
8624 KB |
Output is correct |
71 |
Correct |
10 ms |
8576 KB |
Output is correct |
72 |
Correct |
10 ms |
8576 KB |
Output is correct |
73 |
Correct |
11 ms |
8576 KB |
Output is correct |
74 |
Correct |
10 ms |
8576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8448 KB |
Output is correct |
2 |
Correct |
10 ms |
8576 KB |
Output is correct |
3 |
Correct |
10 ms |
8576 KB |
Output is correct |
4 |
Correct |
9 ms |
8576 KB |
Output is correct |
5 |
Correct |
8 ms |
8448 KB |
Output is correct |
6 |
Correct |
10 ms |
8576 KB |
Output is correct |
7 |
Correct |
8 ms |
8576 KB |
Output is correct |
8 |
Correct |
10 ms |
8576 KB |
Output is correct |
9 |
Correct |
9 ms |
8576 KB |
Output is correct |
10 |
Correct |
10 ms |
8576 KB |
Output is correct |
11 |
Correct |
8 ms |
8576 KB |
Output is correct |
12 |
Correct |
8 ms |
8576 KB |
Output is correct |
13 |
Correct |
8 ms |
8576 KB |
Output is correct |
14 |
Correct |
9 ms |
8576 KB |
Output is correct |
15 |
Correct |
9 ms |
8576 KB |
Output is correct |
16 |
Correct |
10 ms |
8576 KB |
Output is correct |
17 |
Correct |
9 ms |
8576 KB |
Output is correct |
18 |
Correct |
9 ms |
8448 KB |
Output is correct |
19 |
Correct |
9 ms |
8576 KB |
Output is correct |
20 |
Correct |
8 ms |
8448 KB |
Output is correct |
21 |
Correct |
8 ms |
8448 KB |
Output is correct |
22 |
Correct |
10 ms |
8576 KB |
Output is correct |
23 |
Correct |
9 ms |
8448 KB |
Output is correct |
24 |
Correct |
10 ms |
8576 KB |
Output is correct |
25 |
Correct |
10 ms |
8448 KB |
Output is correct |
26 |
Correct |
9 ms |
8576 KB |
Output is correct |
27 |
Correct |
12 ms |
8576 KB |
Output is correct |
28 |
Correct |
8 ms |
8576 KB |
Output is correct |
29 |
Correct |
9 ms |
8576 KB |
Output is correct |
30 |
Correct |
9 ms |
8576 KB |
Output is correct |
31 |
Correct |
9 ms |
8576 KB |
Output is correct |
32 |
Correct |
9 ms |
8448 KB |
Output is correct |
33 |
Correct |
8 ms |
8576 KB |
Output is correct |
34 |
Correct |
10 ms |
8576 KB |
Output is correct |
35 |
Correct |
8 ms |
8576 KB |
Output is correct |
36 |
Correct |
9 ms |
8576 KB |
Output is correct |
37 |
Correct |
8 ms |
8576 KB |
Output is correct |
38 |
Correct |
10 ms |
8576 KB |
Output is correct |
39 |
Correct |
10 ms |
8576 KB |
Output is correct |
40 |
Correct |
11 ms |
8576 KB |
Output is correct |
41 |
Correct |
11 ms |
8576 KB |
Output is correct |
42 |
Correct |
11 ms |
8576 KB |
Output is correct |
43 |
Correct |
12 ms |
8704 KB |
Output is correct |
44 |
Correct |
13 ms |
8576 KB |
Output is correct |
45 |
Correct |
13 ms |
8576 KB |
Output is correct |
46 |
Correct |
12 ms |
8576 KB |
Output is correct |
47 |
Correct |
12 ms |
8576 KB |
Output is correct |
48 |
Correct |
12 ms |
8576 KB |
Output is correct |
49 |
Correct |
12 ms |
8576 KB |
Output is correct |
50 |
Correct |
11 ms |
8576 KB |
Output is correct |
51 |
Correct |
10 ms |
8704 KB |
Output is correct |
52 |
Correct |
11 ms |
8576 KB |
Output is correct |
53 |
Correct |
10 ms |
8576 KB |
Output is correct |
54 |
Correct |
14 ms |
8652 KB |
Output is correct |
55 |
Correct |
11 ms |
8548 KB |
Output is correct |
56 |
Correct |
9 ms |
8576 KB |
Output is correct |
57 |
Correct |
10 ms |
8576 KB |
Output is correct |
58 |
Correct |
11 ms |
8576 KB |
Output is correct |
59 |
Correct |
12 ms |
8576 KB |
Output is correct |
60 |
Correct |
13 ms |
8576 KB |
Output is correct |
61 |
Correct |
10 ms |
8576 KB |
Output is correct |
62 |
Correct |
13 ms |
8576 KB |
Output is correct |
63 |
Correct |
10 ms |
8576 KB |
Output is correct |
64 |
Correct |
10 ms |
8576 KB |
Output is correct |
65 |
Correct |
13 ms |
8704 KB |
Output is correct |
66 |
Correct |
12 ms |
8576 KB |
Output is correct |
67 |
Correct |
11 ms |
8576 KB |
Output is correct |
68 |
Correct |
10 ms |
8576 KB |
Output is correct |
69 |
Correct |
9 ms |
8576 KB |
Output is correct |
70 |
Correct |
10 ms |
8624 KB |
Output is correct |
71 |
Correct |
10 ms |
8576 KB |
Output is correct |
72 |
Correct |
10 ms |
8576 KB |
Output is correct |
73 |
Correct |
11 ms |
8576 KB |
Output is correct |
74 |
Correct |
10 ms |
8576 KB |
Output is correct |
75 |
Correct |
831 ms |
13088 KB |
Output is correct |
76 |
Correct |
918 ms |
16612 KB |
Output is correct |
77 |
Correct |
896 ms |
16740 KB |
Output is correct |
78 |
Correct |
894 ms |
16868 KB |
Output is correct |
79 |
Correct |
146 ms |
16740 KB |
Output is correct |
80 |
Correct |
234 ms |
16752 KB |
Output is correct |
81 |
Correct |
704 ms |
15972 KB |
Output is correct |
82 |
Correct |
677 ms |
16100 KB |
Output is correct |
83 |
Correct |
660 ms |
16100 KB |
Output is correct |
84 |
Correct |
675 ms |
16228 KB |
Output is correct |
85 |
Correct |
674 ms |
16116 KB |
Output is correct |
86 |
Correct |
384 ms |
15972 KB |
Output is correct |
87 |
Correct |
429 ms |
15756 KB |
Output is correct |
88 |
Correct |
671 ms |
15844 KB |
Output is correct |
89 |
Correct |
563 ms |
15972 KB |
Output is correct |
90 |
Correct |
364 ms |
16100 KB |
Output is correct |
91 |
Correct |
241 ms |
15844 KB |
Output is correct |
92 |
Correct |
247 ms |
15844 KB |
Output is correct |
93 |
Correct |
293 ms |
16100 KB |
Output is correct |
94 |
Correct |
217 ms |
16100 KB |
Output is correct |
95 |
Correct |
423 ms |
16228 KB |
Output is correct |
96 |
Correct |
392 ms |
15844 KB |
Output is correct |
97 |
Correct |
451 ms |
16100 KB |
Output is correct |
98 |
Correct |
406 ms |
16260 KB |
Output is correct |
99 |
Correct |
367 ms |
16100 KB |
Output is correct |
100 |
Correct |
299 ms |
15844 KB |
Output is correct |
101 |
Correct |
317 ms |
15844 KB |
Output is correct |
102 |
Correct |
614 ms |
15844 KB |
Output is correct |
103 |
Correct |
456 ms |
15716 KB |
Output is correct |
104 |
Correct |
525 ms |
15972 KB |
Output is correct |
105 |
Correct |
432 ms |
15972 KB |
Output is correct |
106 |
Correct |
479 ms |
16100 KB |
Output is correct |
107 |
Correct |
376 ms |
15844 KB |
Output is correct |
108 |
Correct |
600 ms |
16484 KB |
Output is correct |
109 |
Correct |
514 ms |
16868 KB |
Output is correct |
110 |
Correct |
253 ms |
15204 KB |
Output is correct |
111 |
Correct |
453 ms |
15336 KB |
Output is correct |
112 |
Correct |
392 ms |
15076 KB |
Output is correct |
113 |
Correct |
139 ms |
17220 KB |
Output is correct |