제출 #875448

#제출 시각아이디문제언어결과실행 시간메모리
875448DenkataCake 3 (JOI19_cake3)C++14
0 / 100
1 ms2524 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5+3; ll i,j,p,q,n,m,k,v[maxn],c[maxn]; pair <ll,ll> inp[maxn]; set < pair <ll,int> > vals; set < pair<ll,int> > :: iterator it; ll sum = 0,sum_all=0; bool fl = false; int l,r; void add(ll val,int ind) { sum_all += val; if(vals.size()<m-2) { vals.insert({val,ind}); if(vals.size()==m-2) fl = true,it = vals.begin(),sum = sum_all; return ; } if((*it).first>val) vals.insert({val,ind});//dano ne pravi problemi s it else //if((*it).first<=val) { sum -= (*it).first; sum += val; vals.insert({val,ind}); it++; } } void rem(ll val,int ind) { sum_all-=val; if(vals.size()<=m-2) { vals.erase({val,ind}); sum = -1e18; fl = false; return ; } //dano ne pravi problemi s it if((*it).first>val) { vals.erase({val,ind}); } else //if((*it).first<=val) { sum -= val; it--; vals.erase({val,ind}); sum+=(*it).first; } } void activate(int ll,int rr) { while(r<rr) { r++; add(v[r],r); } //cout<<l<<" "<<r<<" "<<sum<<endl; while(ll<l) { l--; add(v[l],l); } //cout<<l<<" "<<r<<" "<<sum<<endl; while(ll>l) { rem(v[l],l); l++; } //cout<<l<<" "<<r<<" "<<sum<<endl; while(rr<r) { rem(v[r],r); r--; } //cout<<l<<" "<<r<<" "<<sum<<endl; //cout<<l<<" "<<r<<" "<<sum<<endl; } ll overall = -1e18; void solve(int l,int r,int optl,int optr) { if(r<l)return; int mid = (l+r)/2; ll ans = -1e18; int pos = -1; for(int i=optl;i<=min(mid,optr);i++) { if(i+1<=mid-1)activate(i+1,mid-1); if(fl && i+1<=mid-1) { ll tek = v[i]+v[mid]+sum - 2*(c[mid] - c[i]); // cout<<tek<<endl; if(tek>ans) { pos = i; ans = tek; } } } overall = max(overall,ans); if(pos==-1) solve(l,mid-1,optl,optr); else solve(l,mid-1,optl,pos); if(pos!=-1) solve(mid+1,r,pos,optr); else solve(mid+1,r,optl,optr); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(i=1;i<=n;i++) { cin>>inp[i].second>>inp[i].first; } //cout<<endl; sort(inp+1,inp+n+1); for(i=1;i<=n;i++) { v[i] = inp[i].second; c[i] = inp[i].first; // cout<<v[i]<<" "<<c[i]<<endl; } sum_all = v[1]; sum = -1e18; l=r=1; vals.insert({v[1],1}); solve(1,n,1,n); cout<<overall<<endl; return 0; } /* 94 22 17729830 195028137 17729832 195028150 17729830 195028178 17729832 195028140 17729832 195028118 17729836 195028176 17729835 195028180 17729829 195028198 17729829 195028141 17729835 195028132 17729834 195028115 17729829 195028197 17729829 195028160 17729829 195028137 17729834 195028161 17729836 195028115 17729829 195028107 17729834 195028170 17729832 195028132 17729829 195028159 17729833 195028183 17729836 195028178 17729834 195028201 17729830 195028108 17729831 195028145 17729832 195028202 17729829 195028191 17729832 195028150 17729829 195028180 17729835 195028118 17729829 195028176 17729830 195028176 17729834 195028167 17729828 195028160 17729833 195028202 17729829 195028188 17729834 195028107 17729836 195028202 17729830 195028150 17729828 195028137 17729836 195028188 17729831 195028106 17729835 195028176 17729835 195028140 17729834 195028132 17729836 195028137 17729834 195028107 17729834 195028124 17729833 195028137 17729834 195028112 17729834 195028161 17729834 195028154 17729835 195028132 17729832 195028132 17729837 195028202 17729834 195028127 17729830 195028152 17729835 195028150 17729835 195028111 17729829 195028161 17729832 195028137 17729830 195028172 17729829 195028162 17729834 195028161 17729835 195028150 17729834 195028162 17729832 195028114 17729830 195028183 17729829 195028181 17729835 195028113 17729829 195028107 17729835 195028180 17729834 195028145 17729829 195028186 17729837 195028181 17729829 195028159 17729835 195028126 17729836 195028146 17729834 195028118 17729835 195028180 17729832 195028130 17729830 195028172 17729829 195028189 17729834 195028190 17729829 195028150 17729832 195028147 17729833 195028168 17729834 195028120 17729829 195028199 17729834 195028118 17729835 195028178 17729828 195028194 17729837 195028191 17729837 195028170 */

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

cake3.cpp: In function 'void add(ll, int)':
cake3.cpp:16:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   16 |     if(vals.size()<m-2)
      |        ~~~~~~~~~~~^~~~
cake3.cpp:20:23: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   20 |         if(vals.size()==m-2)
      |            ~~~~~~~~~~~^~~~~
cake3.cpp: In function 'void rem(ll, int)':
cake3.cpp:37:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   37 |     if(vals.size()<=m-2)
      |        ~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...