제출 #875434

#제출 시각아이디문제언어결과실행 시간메모리
875434DenkataCake 3 (JOI19_cake3)C++14
0 / 100
1 ms2396 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; bool fl = false; int l,r; void add(ll val,int ind) { if(vals.size()<m-2) { vals.insert({val,ind}); sum+=val; if(vals.size()==m-2) fl = true,it = vals.begin(); 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) { if(vals.size()<=m-2) { vals.erase({val,ind}); sum-=val; 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--; sum+=(*it).first; vals.erase({val,ind}); } } 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<<fl<<" "<<sum<<endl; } ll overall; void solve(int l,int r,int optl,int optr) { if(r<l)return; int mid = (l+r)/2; ll ans = 0; int pos = optl; for(int i=optl;i<=min(mid,optr);i++) { // cout<<i+1<<" "<<mid-1<<" managed :"<<endl; 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); solve(l,mid-1,optl,pos); solve(mid+1,r,pos,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 = v[1]; l=r=1; vals.insert({v[1],1}); it = vals.begin(); solve(1,n,1,n); cout<<overall<<endl; return 0; }

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

cake3.cpp: In function 'void add(ll, int)':
cake3.cpp:15: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]
   15 |     if(vals.size()<m-2)
      |        ~~~~~~~~~~~^~~~
cake3.cpp:19: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]
   19 |         if(vals.size()==m-2)
      |            ~~~~~~~~~~~^~~~~
cake3.cpp: In function 'void rem(ll, int)':
cake3.cpp:35: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]
   35 |     if(vals.size()<=m-2)
      |        ~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...