#pragma GCC optimize("O3")
//#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
#define SZ(x) (int)(x).size()
int K;
int ksum;
multiset<int>tmst;
multiset<int>bmst;
void mINS(int v){
tmst.insert(v);
ksum+=v;
if(tmst.size()>K){
ksum-=*(tmst.begin());
bmst.insert(*tmst.begin());
tmst.erase(tmst.begin());
}
}
void mDEL(int v){
if(bmst.find(v)!=bmst.end()){
bmst.erase(bmst.find(v));
return;
}
ksum-=v;
tmst.erase(tmst.find(v));
if(tmst.size()<K){
if(bmst.size()){
tmst.insert(*(bmst.rbegin()));
ksum+=*bmst.rbegin();
bmst.erase(prev(bmst.end()));
}
}
}
int mlit;int mrit;
int ans;
int n;
pair<int,int>ar[200005];
int opt[200005];
vector<pair<int,int>>targ;vector<pair<int,int>>tbrg;
void solve(vector<pair<int,int>>aarg,vector<pair<int,int>>brg){
vector<int>apt;
for(int i=0;i<aarg.size();i++){
apt.push_back((aarg[i].first+aarg[i].second)/2);
targ.push_back({aarg[i].first,apt.back()});
targ.push_back({apt.back()+1,aarg[i].second});
}
tmst.clear();
bmst.clear();
ksum=0;
int Q=aarg.size();
mlit=n;
mrit=n;
mINS(ar[n].second);
for(int i=Q-1;i>=0;i--){
// cout<<i<<"\n";
int qrpl=apt[i];
int tmx=-1e12;
while(mlit>qrpl-K+1){
mINS(ar[--mlit].second);
}
while(mrit>qrpl){
mDEL(ar[mrit--].second);
}
while(mlit>=brg[i].first){
int cal=-ar[qrpl].first+ar[mlit].first+ksum;
if(cal>=tmx){
opt[i]=mlit;
tmx=cal;
}
ans=max(ans,tmx);
if(mlit==brg[i].first){break;}
mINS(ar[--mlit].second);
}
tbrg.push_back({opt[i],brg[i].second});
tbrg.push_back({brg[i].first,opt[i]});
// cout<<"ll";
}
reverse(tbrg.begin(),tbrg.end());
}
signed main(){
cin>>n>>K;
ans=-1e12;
for(int i=1;i<=n;i++){
cin>>ar[i].second>>ar[i].first;
ar[i].first*=2;
}
sort(ar+1,ar+n+1);
vector<pair<int,int>>vc;vector<pair<int,int>>vc2;
vc.push_back({K,n});
vc2.push_back({1,n-K+1});
int yy=18;
while(yy--){
solve(vc,vc2);
int ok=1;
for(int i=0;i<vc.size();i++){
// cout<<vc[i].first<<" "<<vc[i].second<<" ";
if(vc[i].first!=vc[i].second){ok=0;}
}
// cout<<ans<<" "<<ok<<"\n";
if(ok){break;}
swap(vc,targ);swap(vc2,tbrg);
targ.clear();tbrg.clear();
}
//cout<<"hehe";
cout<<ans<<endl;
}
Compilation message
cake3.cpp: In function 'void mINS(long long int)':
cake3.cpp:16:15: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
16 | if(tmst.size()>K){
| ~~~~~~~~~~~^~
cake3.cpp: In function 'void mDEL(long long int)':
cake3.cpp:29:15: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
29 | if(tmst.size()<K){
| ~~~~~~~~~~~^~
cake3.cpp: In function 'void solve(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
cake3.cpp:48:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0;i<aarg.size();i++){
| ~^~~~~~~~~~~~
cake3.cpp: In function 'int main()':
cake3.cpp:111:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=0;i<vc.size();i++){
| ~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23232 KB |
Output is correct |
2 |
Correct |
17 ms |
23244 KB |
Output is correct |
3 |
Correct |
17 ms |
23228 KB |
Output is correct |
4 |
Correct |
17 ms |
23100 KB |
Output is correct |
5 |
Correct |
18 ms |
23232 KB |
Output is correct |
6 |
Correct |
1 ms |
2392 KB |
Output is correct |
7 |
Correct |
17 ms |
23232 KB |
Output is correct |
8 |
Correct |
17 ms |
23020 KB |
Output is correct |
9 |
Correct |
18 ms |
23232 KB |
Output is correct |
10 |
Correct |
17 ms |
23128 KB |
Output is correct |
11 |
Correct |
17 ms |
23028 KB |
Output is correct |
12 |
Correct |
17 ms |
23012 KB |
Output is correct |
13 |
Correct |
18 ms |
23080 KB |
Output is correct |
14 |
Correct |
17 ms |
23212 KB |
Output is correct |
15 |
Correct |
20 ms |
23232 KB |
Output is correct |
16 |
Correct |
18 ms |
23344 KB |
Output is correct |
17 |
Correct |
17 ms |
23248 KB |
Output is correct |
18 |
Correct |
20 ms |
23176 KB |
Output is correct |
19 |
Correct |
17 ms |
23100 KB |
Output is correct |
20 |
Correct |
16 ms |
23244 KB |
Output is correct |
21 |
Correct |
17 ms |
23244 KB |
Output is correct |
22 |
Correct |
18 ms |
23048 KB |
Output is correct |
23 |
Correct |
17 ms |
23248 KB |
Output is correct |
24 |
Correct |
17 ms |
23232 KB |
Output is correct |
25 |
Correct |
17 ms |
23200 KB |
Output is correct |
26 |
Correct |
16 ms |
23212 KB |
Output is correct |
27 |
Correct |
17 ms |
22992 KB |
Output is correct |
28 |
Correct |
18 ms |
23008 KB |
Output is correct |
29 |
Correct |
18 ms |
23024 KB |
Output is correct |
30 |
Correct |
18 ms |
23232 KB |
Output is correct |
31 |
Correct |
17 ms |
23216 KB |
Output is correct |
32 |
Correct |
17 ms |
23232 KB |
Output is correct |
33 |
Correct |
17 ms |
23084 KB |
Output is correct |
34 |
Correct |
17 ms |
23236 KB |
Output is correct |
35 |
Correct |
1 ms |
2396 KB |
Output is correct |
36 |
Correct |
18 ms |
23132 KB |
Output is correct |
37 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23232 KB |
Output is correct |
2 |
Correct |
17 ms |
23244 KB |
Output is correct |
3 |
Correct |
17 ms |
23228 KB |
Output is correct |
4 |
Correct |
17 ms |
23100 KB |
Output is correct |
5 |
Correct |
18 ms |
23232 KB |
Output is correct |
6 |
Correct |
1 ms |
2392 KB |
Output is correct |
7 |
Correct |
17 ms |
23232 KB |
Output is correct |
8 |
Correct |
17 ms |
23020 KB |
Output is correct |
9 |
Correct |
18 ms |
23232 KB |
Output is correct |
10 |
Correct |
17 ms |
23128 KB |
Output is correct |
11 |
Correct |
17 ms |
23028 KB |
Output is correct |
12 |
Correct |
17 ms |
23012 KB |
Output is correct |
13 |
Correct |
18 ms |
23080 KB |
Output is correct |
14 |
Correct |
17 ms |
23212 KB |
Output is correct |
15 |
Correct |
20 ms |
23232 KB |
Output is correct |
16 |
Correct |
18 ms |
23344 KB |
Output is correct |
17 |
Correct |
17 ms |
23248 KB |
Output is correct |
18 |
Correct |
20 ms |
23176 KB |
Output is correct |
19 |
Correct |
17 ms |
23100 KB |
Output is correct |
20 |
Correct |
16 ms |
23244 KB |
Output is correct |
21 |
Correct |
17 ms |
23244 KB |
Output is correct |
22 |
Correct |
18 ms |
23048 KB |
Output is correct |
23 |
Correct |
17 ms |
23248 KB |
Output is correct |
24 |
Correct |
17 ms |
23232 KB |
Output is correct |
25 |
Correct |
17 ms |
23200 KB |
Output is correct |
26 |
Correct |
16 ms |
23212 KB |
Output is correct |
27 |
Correct |
17 ms |
22992 KB |
Output is correct |
28 |
Correct |
18 ms |
23008 KB |
Output is correct |
29 |
Correct |
18 ms |
23024 KB |
Output is correct |
30 |
Correct |
18 ms |
23232 KB |
Output is correct |
31 |
Correct |
17 ms |
23216 KB |
Output is correct |
32 |
Correct |
17 ms |
23232 KB |
Output is correct |
33 |
Correct |
17 ms |
23084 KB |
Output is correct |
34 |
Correct |
17 ms |
23236 KB |
Output is correct |
35 |
Correct |
1 ms |
2396 KB |
Output is correct |
36 |
Correct |
18 ms |
23132 KB |
Output is correct |
37 |
Correct |
1 ms |
2392 KB |
Output is correct |
38 |
Correct |
26 ms |
23284 KB |
Output is correct |
39 |
Correct |
27 ms |
23196 KB |
Output is correct |
40 |
Correct |
26 ms |
23168 KB |
Output is correct |
41 |
Correct |
29 ms |
23192 KB |
Output is correct |
42 |
Correct |
25 ms |
23276 KB |
Output is correct |
43 |
Correct |
24 ms |
23256 KB |
Output is correct |
44 |
Correct |
26 ms |
23092 KB |
Output is correct |
45 |
Correct |
28 ms |
23088 KB |
Output is correct |
46 |
Correct |
28 ms |
23124 KB |
Output is correct |
47 |
Correct |
27 ms |
23232 KB |
Output is correct |
48 |
Correct |
25 ms |
23092 KB |
Output is correct |
49 |
Correct |
25 ms |
23244 KB |
Output is correct |
50 |
Correct |
25 ms |
23104 KB |
Output is correct |
51 |
Correct |
26 ms |
23288 KB |
Output is correct |
52 |
Correct |
27 ms |
23136 KB |
Output is correct |
53 |
Correct |
26 ms |
23080 KB |
Output is correct |
54 |
Correct |
24 ms |
23112 KB |
Output is correct |
55 |
Correct |
24 ms |
23288 KB |
Output is correct |
56 |
Correct |
24 ms |
23120 KB |
Output is correct |
57 |
Correct |
24 ms |
23224 KB |
Output is correct |
58 |
Correct |
24 ms |
23128 KB |
Output is correct |
59 |
Correct |
21 ms |
23248 KB |
Output is correct |
60 |
Correct |
29 ms |
23728 KB |
Output is correct |
61 |
Correct |
22 ms |
23088 KB |
Output is correct |
62 |
Correct |
21 ms |
23112 KB |
Output is correct |
63 |
Correct |
23 ms |
23224 KB |
Output is correct |
64 |
Correct |
22 ms |
23112 KB |
Output is correct |
65 |
Correct |
26 ms |
23252 KB |
Output is correct |
66 |
Correct |
27 ms |
23240 KB |
Output is correct |
67 |
Correct |
28 ms |
23100 KB |
Output is correct |
68 |
Correct |
26 ms |
23196 KB |
Output is correct |
69 |
Correct |
28 ms |
23096 KB |
Output is correct |
70 |
Correct |
26 ms |
23292 KB |
Output is correct |
71 |
Correct |
25 ms |
23240 KB |
Output is correct |
72 |
Correct |
23 ms |
23288 KB |
Output is correct |
73 |
Correct |
22 ms |
23120 KB |
Output is correct |
74 |
Correct |
3 ms |
2392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23232 KB |
Output is correct |
2 |
Correct |
17 ms |
23244 KB |
Output is correct |
3 |
Correct |
17 ms |
23228 KB |
Output is correct |
4 |
Correct |
17 ms |
23100 KB |
Output is correct |
5 |
Correct |
18 ms |
23232 KB |
Output is correct |
6 |
Correct |
1 ms |
2392 KB |
Output is correct |
7 |
Correct |
17 ms |
23232 KB |
Output is correct |
8 |
Correct |
17 ms |
23020 KB |
Output is correct |
9 |
Correct |
18 ms |
23232 KB |
Output is correct |
10 |
Correct |
17 ms |
23128 KB |
Output is correct |
11 |
Correct |
17 ms |
23028 KB |
Output is correct |
12 |
Correct |
17 ms |
23012 KB |
Output is correct |
13 |
Correct |
18 ms |
23080 KB |
Output is correct |
14 |
Correct |
17 ms |
23212 KB |
Output is correct |
15 |
Correct |
20 ms |
23232 KB |
Output is correct |
16 |
Correct |
18 ms |
23344 KB |
Output is correct |
17 |
Correct |
17 ms |
23248 KB |
Output is correct |
18 |
Correct |
20 ms |
23176 KB |
Output is correct |
19 |
Correct |
17 ms |
23100 KB |
Output is correct |
20 |
Correct |
16 ms |
23244 KB |
Output is correct |
21 |
Correct |
17 ms |
23244 KB |
Output is correct |
22 |
Correct |
18 ms |
23048 KB |
Output is correct |
23 |
Correct |
17 ms |
23248 KB |
Output is correct |
24 |
Correct |
17 ms |
23232 KB |
Output is correct |
25 |
Correct |
17 ms |
23200 KB |
Output is correct |
26 |
Correct |
16 ms |
23212 KB |
Output is correct |
27 |
Correct |
17 ms |
22992 KB |
Output is correct |
28 |
Correct |
18 ms |
23008 KB |
Output is correct |
29 |
Correct |
18 ms |
23024 KB |
Output is correct |
30 |
Correct |
18 ms |
23232 KB |
Output is correct |
31 |
Correct |
17 ms |
23216 KB |
Output is correct |
32 |
Correct |
17 ms |
23232 KB |
Output is correct |
33 |
Correct |
17 ms |
23084 KB |
Output is correct |
34 |
Correct |
17 ms |
23236 KB |
Output is correct |
35 |
Correct |
1 ms |
2396 KB |
Output is correct |
36 |
Correct |
18 ms |
23132 KB |
Output is correct |
37 |
Correct |
1 ms |
2392 KB |
Output is correct |
38 |
Correct |
26 ms |
23284 KB |
Output is correct |
39 |
Correct |
27 ms |
23196 KB |
Output is correct |
40 |
Correct |
26 ms |
23168 KB |
Output is correct |
41 |
Correct |
29 ms |
23192 KB |
Output is correct |
42 |
Correct |
25 ms |
23276 KB |
Output is correct |
43 |
Correct |
24 ms |
23256 KB |
Output is correct |
44 |
Correct |
26 ms |
23092 KB |
Output is correct |
45 |
Correct |
28 ms |
23088 KB |
Output is correct |
46 |
Correct |
28 ms |
23124 KB |
Output is correct |
47 |
Correct |
27 ms |
23232 KB |
Output is correct |
48 |
Correct |
25 ms |
23092 KB |
Output is correct |
49 |
Correct |
25 ms |
23244 KB |
Output is correct |
50 |
Correct |
25 ms |
23104 KB |
Output is correct |
51 |
Correct |
26 ms |
23288 KB |
Output is correct |
52 |
Correct |
27 ms |
23136 KB |
Output is correct |
53 |
Correct |
26 ms |
23080 KB |
Output is correct |
54 |
Correct |
24 ms |
23112 KB |
Output is correct |
55 |
Correct |
24 ms |
23288 KB |
Output is correct |
56 |
Correct |
24 ms |
23120 KB |
Output is correct |
57 |
Correct |
24 ms |
23224 KB |
Output is correct |
58 |
Correct |
24 ms |
23128 KB |
Output is correct |
59 |
Correct |
21 ms |
23248 KB |
Output is correct |
60 |
Correct |
29 ms |
23728 KB |
Output is correct |
61 |
Correct |
22 ms |
23088 KB |
Output is correct |
62 |
Correct |
21 ms |
23112 KB |
Output is correct |
63 |
Correct |
23 ms |
23224 KB |
Output is correct |
64 |
Correct |
22 ms |
23112 KB |
Output is correct |
65 |
Correct |
26 ms |
23252 KB |
Output is correct |
66 |
Correct |
27 ms |
23240 KB |
Output is correct |
67 |
Correct |
28 ms |
23100 KB |
Output is correct |
68 |
Correct |
26 ms |
23196 KB |
Output is correct |
69 |
Correct |
28 ms |
23096 KB |
Output is correct |
70 |
Correct |
26 ms |
23292 KB |
Output is correct |
71 |
Correct |
25 ms |
23240 KB |
Output is correct |
72 |
Correct |
23 ms |
23288 KB |
Output is correct |
73 |
Correct |
22 ms |
23120 KB |
Output is correct |
74 |
Correct |
3 ms |
2392 KB |
Output is correct |
75 |
Correct |
2500 ms |
34144 KB |
Output is correct |
76 |
Correct |
2293 ms |
33916 KB |
Output is correct |
77 |
Correct |
2282 ms |
37896 KB |
Output is correct |
78 |
Correct |
2343 ms |
38188 KB |
Output is correct |
79 |
Correct |
1237 ms |
38284 KB |
Output is correct |
80 |
Correct |
1341 ms |
37588 KB |
Output is correct |
81 |
Correct |
1915 ms |
34304 KB |
Output is correct |
82 |
Correct |
2053 ms |
33708 KB |
Output is correct |
83 |
Correct |
2144 ms |
34728 KB |
Output is correct |
84 |
Correct |
2112 ms |
34560 KB |
Output is correct |
85 |
Correct |
1924 ms |
34500 KB |
Output is correct |
86 |
Correct |
1621 ms |
35000 KB |
Output is correct |
87 |
Correct |
1581 ms |
34872 KB |
Output is correct |
88 |
Correct |
1746 ms |
34048 KB |
Output is correct |
89 |
Correct |
1784 ms |
34872 KB |
Output is correct |
90 |
Correct |
1760 ms |
35944 KB |
Output is correct |
91 |
Correct |
1451 ms |
35500 KB |
Output is correct |
92 |
Correct |
1456 ms |
35508 KB |
Output is correct |
93 |
Correct |
1618 ms |
35520 KB |
Output is correct |
94 |
Correct |
1548 ms |
37220 KB |
Output is correct |
95 |
Correct |
1728 ms |
36112 KB |
Output is correct |
96 |
Correct |
638 ms |
33988 KB |
Output is correct |
97 |
Correct |
743 ms |
34696 KB |
Output is correct |
98 |
Correct |
701 ms |
34368 KB |
Output is correct |
99 |
Correct |
694 ms |
34900 KB |
Output is correct |
100 |
Correct |
623 ms |
34628 KB |
Output is correct |
101 |
Correct |
623 ms |
34624 KB |
Output is correct |
102 |
Correct |
1432 ms |
33576 KB |
Output is correct |
103 |
Correct |
1409 ms |
33708 KB |
Output is correct |
104 |
Correct |
1481 ms |
33764 KB |
Output is correct |
105 |
Correct |
1399 ms |
34724 KB |
Output is correct |
106 |
Correct |
1501 ms |
35044 KB |
Output is correct |
107 |
Correct |
1353 ms |
35128 KB |
Output is correct |
108 |
Correct |
2143 ms |
37832 KB |
Output is correct |
109 |
Correct |
1982 ms |
38536 KB |
Output is correct |
110 |
Correct |
1212 ms |
34288 KB |
Output is correct |
111 |
Correct |
1358 ms |
33472 KB |
Output is correct |
112 |
Correct |
876 ms |
37928 KB |
Output is correct |
113 |
Correct |
180 ms |
18016 KB |
Output is correct |