제출 #411048

#제출 시각아이디문제언어결과실행 시간메모리
411048alireza_kavianiCake 3 (JOI19_cake3)C++11
24 / 100
4075 ms29320 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define all(x) (x).begin(),(x).end() #define X first #define Y second #define sep ' ' #define endl '\n' #define SZ(x) ll(x.size()) const ll MAXN = 1e6 + 10; const ll LOG = 22; const ll INF = 8e18; const ll MOD = 1e9 + 7; //998244353; //1e9 + 9; ll n , m , sum , curl = 1 , curr = 0 , V[MAXN] , C[MAXN] , ans[MAXN]; vector<pll> vec; set<pll> st1; set<pll , greater<pll>> st2; void balance(){ while((SZ(st1) && SZ(st2) && (*st1.begin()) < (*st2.begin())) || SZ(st1) > m - 2){ sum -= (*st1.begin()).X; st2.insert((*st1.begin())); st1.erase(st1.begin()); } while(SZ(st1) < m - 2 && 0 < SZ(st2)){ sum += (*st2.begin()).X; st1.insert((*st2.begin())); st2.erase(st2.begin()); } } void insert(int i){ st1.insert({V[i] , i}); sum += V[i]; balance(); // cout << "insert " << i << sep << sum << endl; } void remove(int i){ if(st1.find({V[i] , i}) != st1.end()){ st1.erase({V[i] , i}); sum -= V[i]; } else{ st2.erase({V[i] , i}); } balance(); // cout << "remove " << i << sep << sum << endl; } void move(int l , int r){ while(curr < r) insert(++curr); while(l < curl) insert(--curl); while(r < curr) remove(curr--); while(curl < l) remove(curl++); } void solve(int l , int r , int optl , int optr){ if(r < l) return; int mid = l + r >> 1 , opt = -1; for(int i = optl ; i <= min(optr , mid - (int)m + 1) ; i++){ move(i + 1 , mid - 1); // cout << i << sep << mid << sep << sum << endl; if(sum + V[mid] + V[i] - C[mid] + C[i] > ans[mid]){ ans[mid] = sum + V[mid] - C[mid] + V[i] + C[i]; opt = i; } } solve(l , mid - 1 , optl , opt); solve(mid + 1 , r , opt , optr); } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); fill(ans , ans + MAXN , -INF); cin >> n >> m; for(int i = 1 ; i <= n ; i++){ cin >> V[i] >> C[i]; vec.push_back({C[i] , V[i]}); } sort(all(vec)); for(int i = 1 ; i <= n ; i++){ C[i] = vec[i - 1].X * 2; V[i] = vec[i - 1].Y; } solve(m , n , 1 , n); ll res = -INF; for(int i = 1 ; i <= n ; i++) res = max(res , ans[i]); cout << res << endl; return 0; } /* */

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

cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = l + r >> 1 , opt = -1;
      |            ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...