Submission #411065

#TimeUsernameProblemLanguageResultExecution timeMemory
411065alireza_kavianiCake 3 (JOI19_cake3)C++11
0 / 100
6 ms8668 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 = (1 << 20); const ll LOG = 20; const ll INF = 8e18; const ll MOD = 1e9 + 7; //998244353; //1e9 + 9; ll n , m , curl = 1 , curr = 0 , V[MAXN] , C[MAXN] , val[MAXN] , ans[MAXN] , fen[2][MAXN]; vector<int> compress; vector<pll> vec; void add(int ind , int x , int val){ for(x++; x < MAXN ; x += x & -x) fen[ind][x] += val; } ll get(int ind , int x){ ll ans = 0; for(x++; x ; x -= x & -x) ans += fen[ind][x]; return ans; } ll find(ll val){ int ans = 0; for(int i = LOG - 1 ; i >= 0 ; i--){ if(fen[0][ans + (1 << i)] < val){ val -= fen[0][ans + (1 << i)]; ans += (1 << i); } } return ans; } ll calc(){ int ind = find(m - 2); return get(1 , ind); } void insert(int i , int x){ add(0 , val[i] , 1 * x); add(1 , val[i] , V[i] * x); // cout << i << sep << x << sep << calc() << endl; } void move(int l , int r){ while(curr < r) insert(++curr , 1); while(l < curl) insert(--curl , 1); while(r < curr) insert(curr-- , -1); while(curl < l) insert(curl++ , -1); } 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; ll sum = calc(); 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]; compress.push_back(V[i]); vec.push_back({C[i] , V[i]}); } sort(all(vec)); sort(all(compress)); compress.resize(unique(all(compress)) - compress.begin()); for(int i = 1 ; i <= n ; i++){ C[i] = vec[i - 1].X * 2; V[i] = vec[i - 1].Y; val[i] = n - (lower_bound(all(compress) , V[i]) - compress.begin()); } 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; } /* */

Compilation message (stderr)

cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  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...