제출 #849285

#제출 시각아이디문제언어결과실행 시간메모리
849285Hakiers휴가 (IOI14_holiday)C++17
100 / 100
255 ms9508 KiB
#include <bits/stdc++.h> #include"holiday.h" using namespace std; const int BASE = 1 << 17; pair<int, int> atrac[BASE]; long long dp[BASE]; long long dp2[BASE]; int globD; long long res = 0; struct Node{ long long sum; int count; }; Node TREE[BASE << 1]; void update(int v, int sum){ v+= BASE; if(sum < 0) TREE[v].count = 0; else TREE[v].count = 1; TREE[v].sum += sum; v/=2; while(v > 0){ int l = 2*v, r = 2*v + 1; TREE[v].count = TREE[l].count + TREE[r].count; TREE[v].sum = TREE[l].sum + TREE[r].sum; v/=2; } } long long find(int v, int a, int b, int val){ if(TREE[v].count == 0 || val <= 0) return 0; else if(TREE[v].count <= val) return TREE[v].sum; else{ int l = 2*v, r = 2*v + 1, mid = (a+b)/2;; if(TREE[r].count >= val) return find(r, mid+1, b, val); return TREE[r].sum + find(l, a, mid, val - TREE[r].count); } } int L = 0, R = -1; void mo(int a, int b){ while(L > a){ L--; update(atrac[L].second, atrac[L].first); } while(R < b){ R++; update(atrac[R].second, atrac[R].first); } while(L < a){ update(atrac[L].second, -atrac[L].first); L++; } while(R > b){ update(atrac[R].second, -atrac[R].first); R--; } } void dpc(int l, int r, int optl, int optr, int start){ int mid = (l+r)/2; if(r < l) return; mo(optl, mid); int opt = optl; for(int i = optl; i <= min(mid, optr) && i <= start; i++){ int cost = (start - i) + (mid - i); //cout << mid << " " << i << " " << cost << endl; if(globD - cost > 0){ long long earn = find(1, 0, BASE-1, globD - cost); //cout << mid << " " << i << " " << earn << endl; if(dp[mid] <= earn){ dp[mid] = earn; res = max(res, earn); opt = i; } } update(atrac[i].second, -atrac[i].first); ++L; } dpc(l, mid-1, optl, opt, start); dpc(mid+1, r, opt, optr, start); } void dpc2(int l, int r, int optl, int optr, int start){ int mid = (l+r)/2; if(r < l) return; mo(mid, optr); int opt = optr; for(int i = optr; i >= max(mid, optl) && i >= start; i--){ int cost = (i - start) + (i - mid); if(globD - cost > 0){ long long earn = find(1, 0, BASE-1, globD - cost); if(dp2[mid] <= earn){ dp2[mid] = earn; res = max(res, earn); opt = i; } } update(atrac[i].second, -atrac[i].first); --R; } dpc2(l, mid-1, optl, opt, start); dpc2(mid+1, r, opt, optr, start); } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { /*int main(){ int n, start, d; vector<int> attraction; cin >> n >> start >> d; for(int i = 0; i < n; i++){ int xd; cin >> xd; attraction.push_back(xd); } */ vector<pair<int, int>> pos; for(int i = 0; i < n; i++) pos.push_back({attraction[i], i}); sort(pos.begin(), pos.end()); for(int id = 0; id < n; id++) atrac[pos[id].second] = {pos[id].first, id}; globD = d; dpc(start, n-1, 0, n-1, start); dpc2(0, start, 0, n-1, start); //cout << res << endl; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...