제출 #132604

#제출 시각아이디문제언어결과실행 시간메모리
132604someone_aa휴가 (IOI14_holiday)C++17
47 / 100
204 ms65536 KiB
#include <bits/stdc++.h> #include "holiday.h" #define ll long long #define pb push_back #define mp make_pair using namespace std; const int maxn = 100500; ll value[maxn], d; int arr[maxn]; /*class node { public: ll sum; int cnt; node *leftchild, *rightchild; node(ll _sum, ll _cnt) { sum = _sum; cnt = _cnt; } node(node *a, node *b) { leftchild = a; rightchild = b; sum = a->sum + b->sum; cnt = a->cnt + b->cnt; } };*/ vector<ll>sum, cnt; vector<int>l, r; int makenewleaf(ll _sum, ll _cnt) { sum.pb(_sum); cnt.pb(_cnt); l.pb(-1); r.pb(-1); return int(sum.size()-1); } int makenewparent(int _l, int _r) { sum.pb(sum[_l] + sum[_r]); cnt.pb(cnt[_l] + cnt[_r]); l.pb(_l); r.pb(_r); return int(sum.size()-1); } int zeroleaf; int build(int li=1, int ri=d) { if(li == ri) return zeroleaf; else { int mid = (li + ri) / 2; return makenewparent(build(li, mid), build(mid+1, ri)); } } int update(int curr, ll uind, ll uval, int li=1, int ri=d) { if(li == ri) { return makenewleaf(sum[curr] + uval, cnt[curr] + 1); } else { int mid = (li + ri) / 2; if(uind <= mid) return makenewparent(update(l[curr], uind, uval, li, mid), r[curr]); else return makenewparent(l[curr], update(r[curr], uind, uval, mid+1, ri)); } } ll solve(int p, int pm, ll k, int li=1, int ri=d) { ll total = cnt[p] - cnt[pm]; //cout<<li<<" "<<ri<<" -> "<<total<<", "<<k<<"\n"; if(k == 0) return 0LL; if(total < k) return (sum[p] - sum[pm]); if(li == ri) { return k * value[li]; } else { int mid = (li + ri) / 2; ll total_right = cnt[r[p]] - cnt[r[pm]]; if(total_right >= k) return solve(r[p], r[pm], k, mid+1, ri); else return (sum[r[p]] - sum[r[pm]]) + solve(l[p], l[pm], k - total_right, li, mid); } } int prefix[maxn]; set<int>st; map<int,int>ind; int n, start, c; ll dp[maxn]; void solvedp(int l=1, int r=start, int optl=start, int optr=n) { if(l > r) return; int mid = (l + r) / 2; // calculate dp[mid] dp[mid] = -1; int optmid = -1; for(int i=optl;i<=optr;i++) { ll walk = i - mid + min(start - mid, i - start); ll curr = solve(prefix[i], prefix[mid-1], max(0LL, c - walk)); if(curr > dp[mid]) { dp[mid] = curr; optmid = i; } } solvedp(l, mid-1, optl, optmid); solvedp(mid+1, r, optmid, optr); } ll findMaxAttraction(int _n, int _start, int _c, int _attractions[]) { //ifstream fin("input.txt"); n = _n; start = _start; c = _c; //cin>>n>>start>>c; start++; for(int i=0;i<n;i++) { arr[i] = _attractions[i]; st.insert(arr[i]); } int br = 1; for(int i:st) { value[br] = i; ind[i] = br++; } d = br - 1; for(int i=n-1;i>=0;i--) { arr[i+1] = ind[arr[i]]; } zeroleaf = makenewleaf(0LL, 0LL); int curr = build(); prefix[0] = curr; for(int i=1;i<=n;i++) { prefix[i] = prefix[i-1]; prefix[i] = update(prefix[i], arr[i], value[arr[i]]); //cout<<i<<": "<<sum[prefix[i]]<<"\n"; } //cout<<solve(prefix[4], prefix[0], 3)<<"A\n"; solvedp(); ll result = 0LL; for(int i=1;i<=n;i++) { result = max(result, dp[i]); } return result; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...