제출 #331195

#제출 시각아이디문제언어결과실행 시간메모리
331195EIMONIMCake 3 (JOI19_cake3)C++14
0 / 100
1 ms364 KiB
#include <bits/stdc++.h> #define int int64_t #define vi vector<int> #define ii pair<int,int> #define vb vector<bool> #define vvi vector<vi> #define vvb vector<vb> #define vii vector<ii> #define vvii vector<vii> #define x first #define y second #define pb push_back #define loop(i,s,e) for(int i=s;i<e;i++) #define loopr(i,s,e) for(int i=e-1;i>=s;i--) #define chkmax(a,b) a = max(a,b) #define chkmin(a,b) a=min(a,b) #define all(x) x.begin(),x.end() using namespace std; const int INF = 1e18, MOD = 1e9 + 7; int n,m; vii a; struct Data{ int l=0,r=-1; set<ii> best, reserve; int res = 0; void add(int i){ best.insert({a[i].y, i}); res += a[i].y; if (best.size()>m){ auto it = best.begin(); res -= it->x; reserve.insert(*it); best.erase(it); } } void remove(int i){ auto it = best.find({a[i].y, i}); if (it != best.end()){ res -= it->x; best.erase(it); if (reserve.size()){ auto rit = --reserve.end(); best.insert(*rit); res += rit->x; reserve.erase(rit); } } else{ reserve.erase({a[i].y, i}); } } void update(int a, int b){ /*if (a > r){ while(l<=r) remove(l++); l = a, r = a-1; }*/ while(b>r) add(++r); while(a<l) add(--l); while(b<r) remove(r--); while(a>l) remove(l++); } int get(){ if (best.size()<m) return -INF; return res; } } data; int ans = 0; void solve(int l, int r, int optl, int optr){ if (r<=l) return ; int i = (l+r)/2; int ll = max(optl, i+m-1); int opt = ll, bestv = 0; loop(j,ll,optr+1){ data.update(i, j); int v = data.get() - (a[j].x - a[i].x); if (bestv < v){ bestv = v; opt = j; } } chkmax(ans, bestv); solve(i+1, r, opt, optr); solve(l, i, optl, opt); } int32_t main(){ ios_base::sync_with_stdio(false); cin>>n>>m; a.resize(n); loop(i,0,n) cin>>a[i].y>>a[i].x, a[i].x*=2; sort(all(a)); solve(0,n-m,0,n); cout<<ans<<endl; return 0; } /* color a cls g++ cake3.cpp -o a & a 5 3 2 1 4 2 6 4 8 8 10 16 */

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

cake3.cpp: In member function 'void Data::add(int64_t)':
cake3.cpp:32:24: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   32 |         if (best.size()>m){
      |             ~~~~~~~~~~~^~
cake3.cpp: In member function 'int64_t Data::get()':
cake3.cpp:66:24: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   66 |         if (best.size()<m) return -INF;
      |             ~~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...