제출 #157866

#제출 시각아이디문제언어결과실행 시간메모리
157866usernameCake 3 (JOI19_cake3)C++14
24 / 100
4006 ms15252 KiB
#pragma GCC optimize("O3") #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include<ext/rope> using namespace __gnu_pbds; using namespace __gnu_cxx; #define tr(it,a) for(auto it:a) #define pob pop_back #define pf push_front #define pof pop_front #define umin(x,y) (x=min(x,(y))) #define umax(x,y) (x=max(x,(y))) //#define mid ((l+r)/2) #define lch (idx*2+1) #define rch (idx*2+2) // #include<bits/stdc++.h> #define int int_fast64_t using namespace std; typedef pair<int,int> pii; #define rep(i,j,k) for(register int i=(j);i<(k);++i) #define rrep(i,j,k) for(int i=int(j)-1;i>=(k);--i) #define all(a) a.begin(),a.end() #define pb push_back #define f first #define s second #define endl '\n' // #define __debug #ifdef __debug #define ios (void)0 #define pr(...) cerr<<__VA_ARGS__ #define ar(a,s,t) {rep(zy,s,t)pr(a[zy]<<' ');pr(endl);} #else #define ios cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false) #define pr(...) (void)0 #define ar(...) (void)0 #endif // const int maxn=2e5+9,inf=1ll<<40; int n,m,ll,rr,sum=0,res=-inf; pii a[maxn]; multiset<int>s1,s2; inline void ins(int x){ s2.insert(x),sum+=x; auto it=s2.begin(); s1.insert(*it),s2.erase(it),sum-=*it; } inline void rem(int x){ if(s1.count(x))s1.erase(s1.find(x)); else{ s2.erase(s2.find(x)),sum-=x; auto it=--s1.end(); s2.insert(*it),sum+=*it,s1.erase(it); } } void sol(int l1,int r1,int l2,int r2){ if(l1>r1)return; int mid=(l1+r1)/2,k=max(mid,l2); while(rr<k)ins(a[rr++].s); while(ll>mid)ins(a[--ll].s); while(rr>k)rem(a[--rr].s); while(ll<mid)rem(a[ll++].s); pii opt={sum-2*(a[l2-1].f-a[mid].f),k}; rep(i,k,r2){ ins(a[rr++].s); umax(opt,pii(sum-2*(a[i].f-a[mid].f),i+1)); } umax(res,opt.f); sol(l1,mid-1,l2,opt.s); sol(mid+1,r1,opt.s,r2); } main(){ ios; cin>>n>>m; rep(i,0,n)cin>>a[i].s>>a[i].f; sort(a,a+n); rep(i,0,m)s2.insert(-inf),sum-=inf; ll=rr=(n-m)/2; sol(0,n-m,m,n); cout<<res<<endl; }

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp:76:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...