#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <time.h>
using namespace std;
pair < long long , long long > all[200005];
long long pre[200005]={0};
//vector < long long > tt;
struct A
{
long long here;
long long sum;
long long rnd;
long long nxl,nxr;
long long sz=0;
}Node[200005];
long long root=0;
long long now;
void UPD(long long here)
{
Node[here].sum=Node[Node[here].nxl].sum+Node[Node[here].nxr].sum+Node[here].here;
Node[here].sz=Node[Node[here].nxl].sz+Node[Node[here].nxr].sz+1;
}
long long Merge(long long a,long long b)
{
if(a==0) return b;
if(b==0) return a;
if(Node[a].rnd>Node[b].rnd)
{
Node[a].nxr=Merge(Node[a].nxr,b);
UPD(a);
return a;
}
else
{
Node[b].nxl=Merge(a,Node[b].nxl);
UPD(b);
return b;
}
}
pair < long long , long long > split1(long long here,long long con)
{
pair < long long , long long > tt;
if(here==0) return make_pair(0,0);
if(Node[here].here>con)
{
tt=split1(Node[here].nxl,con);
Node[here].nxl=tt.second;
UPD(here);
tt.second=here;
return tt;
}
else
{
tt=split1(Node[here].nxr,con);
Node[here].nxr=tt.first;
UPD(here);
tt.first=here;
return tt;
}
}
pair < long long , long long > split2(long long here,long long con)
{
pair < long long , long long > tt;
if(here==0) return make_pair(0,0);
if(Node[Node[here].nxl].sz>=con)
{
tt=split2(Node[here].nxl,con);
Node[here].nxl=tt.second;
UPD(here);
tt.second=here;
return tt;
}
else
{
tt=split2(Node[here].nxr,con-Node[Node[here].nxl].sz-1);
Node[here].nxr=tt.first;
UPD(here);
tt.first=here;
return tt;
}
}
void BFS(long long here)
{
if(here==0) return ;
BFS(Node[here].nxl);
printf("%lld\n",Node[here].here);
BFS(Node[here].nxr);
}
int main()
{
srand(time(NULL));
long long N,M,ans=-1e18,i,j,k,xx=0;
pair < long long , long long > tt;
scanf("%lld %lld",&N,&M);
for(i=1;i<=N;i++)
{
scanf("%lld %lld",&all[i].second,&all[i].first);
}
sort(all+1,all+N+1);
for(i=1;i<=N;i++)
{
root=0;
Node[0].here=0;
Node[0].sum=0;
Node[0].sz=0;
for(j=i;j<=N;j++)
{
Node[j-i+1].here=all[j].second;
Node[j-i+1].sz=1;
Node[j-i+1].nxl=0;
Node[j-i+1].nxr=0;
Node[j-i+1].sum=all[j].second;
Node[j-i+1].rnd=rand();
tt=split1(root,all[j].second);
root=Merge(Merge(tt.first,j-i+1),tt.second);
//printf("aa %lld %lld\n",i,j);
//BFS(root);
//printf("\n");
if(j-i+1>=M)
{
xx=0;
tt=split2(root,j-i+1-M);
//BFS(tt.second);
//printf("%lld\n",Node[tt.second].sum);
xx=Node[tt.second].sum;
xx-=2*(all[j].first-all[i].first);
ans=max(ans,xx);
root=Merge(tt.first,tt.second);
}
}
}
printf("%lld\n",ans);
return 0;
}
Compilation message
cake3.cpp: In function 'int main()':
cake3.cpp:98:33: warning: unused variable 'k' [-Wunused-variable]
98 | long long N,M,ans=-1e18,i,j,k,xx=0;
| ^
cake3.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | scanf("%lld %lld",&N,&M);
| ~~~~~^~~~~~~~~~~~~~~~~~~
cake3.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
103 | scanf("%lld %lld",&all[i].second,&all[i].first);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
6 ms |
9708 KB |
Output is correct |
4 |
Correct |
6 ms |
9708 KB |
Output is correct |
5 |
Correct |
6 ms |
9708 KB |
Output is correct |
6 |
Correct |
6 ms |
9708 KB |
Output is correct |
7 |
Correct |
6 ms |
9708 KB |
Output is correct |
8 |
Correct |
7 ms |
9708 KB |
Output is correct |
9 |
Correct |
7 ms |
9708 KB |
Output is correct |
10 |
Correct |
8 ms |
9708 KB |
Output is correct |
11 |
Correct |
8 ms |
9708 KB |
Output is correct |
12 |
Correct |
6 ms |
9708 KB |
Output is correct |
13 |
Correct |
6 ms |
9708 KB |
Output is correct |
14 |
Correct |
6 ms |
9708 KB |
Output is correct |
15 |
Correct |
6 ms |
9708 KB |
Output is correct |
16 |
Correct |
6 ms |
9708 KB |
Output is correct |
17 |
Correct |
6 ms |
9708 KB |
Output is correct |
18 |
Correct |
6 ms |
9708 KB |
Output is correct |
19 |
Correct |
6 ms |
9708 KB |
Output is correct |
20 |
Correct |
8 ms |
9708 KB |
Output is correct |
21 |
Correct |
6 ms |
9708 KB |
Output is correct |
22 |
Correct |
6 ms |
9708 KB |
Output is correct |
23 |
Correct |
7 ms |
9708 KB |
Output is correct |
24 |
Correct |
6 ms |
9708 KB |
Output is correct |
25 |
Correct |
7 ms |
9708 KB |
Output is correct |
26 |
Correct |
7 ms |
9708 KB |
Output is correct |
27 |
Correct |
6 ms |
9708 KB |
Output is correct |
28 |
Correct |
7 ms |
9708 KB |
Output is correct |
29 |
Correct |
6 ms |
9708 KB |
Output is correct |
30 |
Correct |
7 ms |
9708 KB |
Output is correct |
31 |
Correct |
6 ms |
9708 KB |
Output is correct |
32 |
Correct |
7 ms |
9708 KB |
Output is correct |
33 |
Correct |
6 ms |
9708 KB |
Output is correct |
34 |
Correct |
6 ms |
9708 KB |
Output is correct |
35 |
Correct |
7 ms |
9708 KB |
Output is correct |
36 |
Correct |
6 ms |
9708 KB |
Output is correct |
37 |
Correct |
6 ms |
9708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
6 ms |
9708 KB |
Output is correct |
4 |
Correct |
6 ms |
9708 KB |
Output is correct |
5 |
Correct |
6 ms |
9708 KB |
Output is correct |
6 |
Correct |
6 ms |
9708 KB |
Output is correct |
7 |
Correct |
6 ms |
9708 KB |
Output is correct |
8 |
Correct |
7 ms |
9708 KB |
Output is correct |
9 |
Correct |
7 ms |
9708 KB |
Output is correct |
10 |
Correct |
8 ms |
9708 KB |
Output is correct |
11 |
Correct |
8 ms |
9708 KB |
Output is correct |
12 |
Correct |
6 ms |
9708 KB |
Output is correct |
13 |
Correct |
6 ms |
9708 KB |
Output is correct |
14 |
Correct |
6 ms |
9708 KB |
Output is correct |
15 |
Correct |
6 ms |
9708 KB |
Output is correct |
16 |
Correct |
6 ms |
9708 KB |
Output is correct |
17 |
Correct |
6 ms |
9708 KB |
Output is correct |
18 |
Correct |
6 ms |
9708 KB |
Output is correct |
19 |
Correct |
6 ms |
9708 KB |
Output is correct |
20 |
Correct |
8 ms |
9708 KB |
Output is correct |
21 |
Correct |
6 ms |
9708 KB |
Output is correct |
22 |
Correct |
6 ms |
9708 KB |
Output is correct |
23 |
Correct |
7 ms |
9708 KB |
Output is correct |
24 |
Correct |
6 ms |
9708 KB |
Output is correct |
25 |
Correct |
7 ms |
9708 KB |
Output is correct |
26 |
Correct |
7 ms |
9708 KB |
Output is correct |
27 |
Correct |
6 ms |
9708 KB |
Output is correct |
28 |
Correct |
7 ms |
9708 KB |
Output is correct |
29 |
Correct |
6 ms |
9708 KB |
Output is correct |
30 |
Correct |
7 ms |
9708 KB |
Output is correct |
31 |
Correct |
6 ms |
9708 KB |
Output is correct |
32 |
Correct |
7 ms |
9708 KB |
Output is correct |
33 |
Correct |
6 ms |
9708 KB |
Output is correct |
34 |
Correct |
6 ms |
9708 KB |
Output is correct |
35 |
Correct |
7 ms |
9708 KB |
Output is correct |
36 |
Correct |
6 ms |
9708 KB |
Output is correct |
37 |
Correct |
6 ms |
9708 KB |
Output is correct |
38 |
Correct |
828 ms |
9708 KB |
Output is correct |
39 |
Correct |
929 ms |
9836 KB |
Output is correct |
40 |
Correct |
715 ms |
9836 KB |
Output is correct |
41 |
Correct |
694 ms |
9836 KB |
Output is correct |
42 |
Correct |
696 ms |
9860 KB |
Output is correct |
43 |
Correct |
621 ms |
9836 KB |
Output is correct |
44 |
Correct |
807 ms |
9836 KB |
Output is correct |
45 |
Correct |
928 ms |
9836 KB |
Output is correct |
46 |
Correct |
958 ms |
9812 KB |
Output is correct |
47 |
Correct |
899 ms |
9812 KB |
Output is correct |
48 |
Correct |
799 ms |
9836 KB |
Output is correct |
49 |
Correct |
827 ms |
9708 KB |
Output is correct |
50 |
Correct |
822 ms |
9836 KB |
Output is correct |
51 |
Correct |
793 ms |
9836 KB |
Output is correct |
52 |
Correct |
730 ms |
9812 KB |
Output is correct |
53 |
Correct |
806 ms |
9812 KB |
Output is correct |
54 |
Correct |
755 ms |
9964 KB |
Output is correct |
55 |
Correct |
677 ms |
9836 KB |
Output is correct |
56 |
Correct |
637 ms |
9708 KB |
Output is correct |
57 |
Correct |
645 ms |
9836 KB |
Output is correct |
58 |
Correct |
642 ms |
9708 KB |
Output is correct |
59 |
Correct |
376 ms |
9836 KB |
Output is correct |
60 |
Correct |
481 ms |
9812 KB |
Output is correct |
61 |
Correct |
447 ms |
9856 KB |
Output is correct |
62 |
Correct |
344 ms |
9708 KB |
Output is correct |
63 |
Correct |
607 ms |
9708 KB |
Output is correct |
64 |
Correct |
396 ms |
9812 KB |
Output is correct |
65 |
Correct |
774 ms |
9836 KB |
Output is correct |
66 |
Correct |
764 ms |
9868 KB |
Output is correct |
67 |
Correct |
833 ms |
9708 KB |
Output is correct |
68 |
Correct |
765 ms |
9708 KB |
Output is correct |
69 |
Correct |
689 ms |
9836 KB |
Output is correct |
70 |
Correct |
758 ms |
9836 KB |
Output is correct |
71 |
Correct |
847 ms |
9812 KB |
Output is correct |
72 |
Correct |
688 ms |
9836 KB |
Output is correct |
73 |
Correct |
464 ms |
9708 KB |
Output is correct |
74 |
Correct |
735 ms |
9812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
6 ms |
9708 KB |
Output is correct |
4 |
Correct |
6 ms |
9708 KB |
Output is correct |
5 |
Correct |
6 ms |
9708 KB |
Output is correct |
6 |
Correct |
6 ms |
9708 KB |
Output is correct |
7 |
Correct |
6 ms |
9708 KB |
Output is correct |
8 |
Correct |
7 ms |
9708 KB |
Output is correct |
9 |
Correct |
7 ms |
9708 KB |
Output is correct |
10 |
Correct |
8 ms |
9708 KB |
Output is correct |
11 |
Correct |
8 ms |
9708 KB |
Output is correct |
12 |
Correct |
6 ms |
9708 KB |
Output is correct |
13 |
Correct |
6 ms |
9708 KB |
Output is correct |
14 |
Correct |
6 ms |
9708 KB |
Output is correct |
15 |
Correct |
6 ms |
9708 KB |
Output is correct |
16 |
Correct |
6 ms |
9708 KB |
Output is correct |
17 |
Correct |
6 ms |
9708 KB |
Output is correct |
18 |
Correct |
6 ms |
9708 KB |
Output is correct |
19 |
Correct |
6 ms |
9708 KB |
Output is correct |
20 |
Correct |
8 ms |
9708 KB |
Output is correct |
21 |
Correct |
6 ms |
9708 KB |
Output is correct |
22 |
Correct |
6 ms |
9708 KB |
Output is correct |
23 |
Correct |
7 ms |
9708 KB |
Output is correct |
24 |
Correct |
6 ms |
9708 KB |
Output is correct |
25 |
Correct |
7 ms |
9708 KB |
Output is correct |
26 |
Correct |
7 ms |
9708 KB |
Output is correct |
27 |
Correct |
6 ms |
9708 KB |
Output is correct |
28 |
Correct |
7 ms |
9708 KB |
Output is correct |
29 |
Correct |
6 ms |
9708 KB |
Output is correct |
30 |
Correct |
7 ms |
9708 KB |
Output is correct |
31 |
Correct |
6 ms |
9708 KB |
Output is correct |
32 |
Correct |
7 ms |
9708 KB |
Output is correct |
33 |
Correct |
6 ms |
9708 KB |
Output is correct |
34 |
Correct |
6 ms |
9708 KB |
Output is correct |
35 |
Correct |
7 ms |
9708 KB |
Output is correct |
36 |
Correct |
6 ms |
9708 KB |
Output is correct |
37 |
Correct |
6 ms |
9708 KB |
Output is correct |
38 |
Correct |
828 ms |
9708 KB |
Output is correct |
39 |
Correct |
929 ms |
9836 KB |
Output is correct |
40 |
Correct |
715 ms |
9836 KB |
Output is correct |
41 |
Correct |
694 ms |
9836 KB |
Output is correct |
42 |
Correct |
696 ms |
9860 KB |
Output is correct |
43 |
Correct |
621 ms |
9836 KB |
Output is correct |
44 |
Correct |
807 ms |
9836 KB |
Output is correct |
45 |
Correct |
928 ms |
9836 KB |
Output is correct |
46 |
Correct |
958 ms |
9812 KB |
Output is correct |
47 |
Correct |
899 ms |
9812 KB |
Output is correct |
48 |
Correct |
799 ms |
9836 KB |
Output is correct |
49 |
Correct |
827 ms |
9708 KB |
Output is correct |
50 |
Correct |
822 ms |
9836 KB |
Output is correct |
51 |
Correct |
793 ms |
9836 KB |
Output is correct |
52 |
Correct |
730 ms |
9812 KB |
Output is correct |
53 |
Correct |
806 ms |
9812 KB |
Output is correct |
54 |
Correct |
755 ms |
9964 KB |
Output is correct |
55 |
Correct |
677 ms |
9836 KB |
Output is correct |
56 |
Correct |
637 ms |
9708 KB |
Output is correct |
57 |
Correct |
645 ms |
9836 KB |
Output is correct |
58 |
Correct |
642 ms |
9708 KB |
Output is correct |
59 |
Correct |
376 ms |
9836 KB |
Output is correct |
60 |
Correct |
481 ms |
9812 KB |
Output is correct |
61 |
Correct |
447 ms |
9856 KB |
Output is correct |
62 |
Correct |
344 ms |
9708 KB |
Output is correct |
63 |
Correct |
607 ms |
9708 KB |
Output is correct |
64 |
Correct |
396 ms |
9812 KB |
Output is correct |
65 |
Correct |
774 ms |
9836 KB |
Output is correct |
66 |
Correct |
764 ms |
9868 KB |
Output is correct |
67 |
Correct |
833 ms |
9708 KB |
Output is correct |
68 |
Correct |
765 ms |
9708 KB |
Output is correct |
69 |
Correct |
689 ms |
9836 KB |
Output is correct |
70 |
Correct |
758 ms |
9836 KB |
Output is correct |
71 |
Correct |
847 ms |
9812 KB |
Output is correct |
72 |
Correct |
688 ms |
9836 KB |
Output is correct |
73 |
Correct |
464 ms |
9708 KB |
Output is correct |
74 |
Correct |
735 ms |
9812 KB |
Output is correct |
75 |
Execution timed out |
4048 ms |
12652 KB |
Time limit exceeded |
76 |
Halted |
0 ms |
0 KB |
- |