Submission #1244327

#TimeUsernameProblemLanguageResultExecution timeMemory
1244327hainam2k9Cake 3 (JOI19_cake3)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> #define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0) #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout) #define ll long long #define ull unsigned long long #define i128 __int128 #define db long double #define sz(a) ((int)(a).size()) #define pb emplace_back #define pf emplace_front #define pob pop_back #define pof pop_front #define lb lower_bound #define ub upper_bound #define fi first #define se second #define ins emplace #define mp make_pair using namespace std; const int MOD = 1e9+7, MAXN = 2e5+5; const string NAME = ""; int n,m,L,R; ll rs=0,sum=0,preMAX[MAXN]; pair<int,int> p[MAXN]; multiset<int, greater<int>> ms1,ms2; void add(int x){ if(sz(ms1)<m) ms1.ins(x), sum+=x; else if(*ms1.rbegin()<x) ms2.ins(*ms1.rbegin()), sum-=*ms1.rbegin(), ms1.erase(prev(ms1.end())), ms1.ins(x), sum+=x; else ms2.ins(x); } void rem(int x){ if(!ms2.empty()&&*ms2.begin()>=x) ms2.erase(ms2.find(x)); else{ ms1.erase(ms1.find(x)), sum-=x; if(!ms2.empty()) sum+=*ms2.begin(), ms1.ins(*ms2.begin()), ms2.erase(ms2.begin()); } } void dnc(int l, int r, int optl, int optr){ if(l>r||optl>optr) return; int mid=(l+r)>>1; while(R>mid-1) rem(p[R--].se); while(R<mid-1) add(p[++R].se); while(L>min(mid-m,optr)) add(p[--L].se); while(L<min(mid-m,optr)) rem(p[L++].se); pair<ll,int> opt={-1e18,0}; for(int i = min(optr,mid-m); i>=optl; --i){ if(L>i) add(p[--L].se); opt=max(opt,mp(preMAX[i-1]-2ll*p[mid].fi+p[mid].se+sum,i)); } rs=max(rs,opt.fi); dnc(l,mid-1,optl,opt.se); dnc(mid+1,r,opt.se,optr); } int main() { tt; if(fopen((NAME + ".INP").c_str(), "r")) fo; cin >> n >> m; for(int i = 1; i<=n; ++i) cin >> p[i].se >> p[i].fi; sort(p+1,p+n+1); preMAX[1]=p[1].se+2ll*p[1].fi; for(int i = 2; i<=n; ++i) preMAX[i]=max(preMAX[i-1],p[i].se+2ll*p[i].fi); m-=2, L=2, R=n-m; for(int i = 2; i<=n-m; ++i) add(p[i].se); dnc(m+2,n,2,n-m); cout << rs; }

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:57:45: note: in expansion of macro 'fo'
   57 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
cake3.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:57:45: note: in expansion of macro 'fo'
   57 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...