Submission #286049

#TimeUsernameProblemLanguageResultExecution timeMemory
286049emanIaicepsaHoliday (IOI14_holiday)C++14
23 / 100
1469 ms36916 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define vi vector<int> #define fi first #define se second #define pii pair<ll,ll> #define all(n) (n).begin(),(n).end() #define pb push_back #define dbg(x) cerr<<#x<<" = "<<x<<'\n'; struct Persistent_tree{ ll l, r; ll tot, cnt; }tr[8000005]; ll idx = 0, rt[100005]; void insert(ll copy, ll &now, ll val, ll L, ll R){ now = ++idx; if(copy) tr[now] = tr[copy]; tr[now].cnt++; tr[now].tot += val; if(L == R){ /* cout<<now<<'\n'; */ return; } ll M = (L+R)/2; if(val <= M) insert(tr[copy].l, tr[now].l, val, L, M); else insert(tr[copy].r, tr[now].r, val, M+1, R); } ll query(int lid, int rid, int num){ if(tr[rid].cnt - tr[lid].cnt <= num) return tr[rid].tot - tr[lid].tot; if(num <= 0) return 0; int Rr = tr[rid].r, Rl = tr[rid].l, Lr = tr[lid].r, Ll = tr[lid].l; if(!Rr && !Rl) return (tr[rid].tot - tr[lid].tot) / (tr[rid].cnt - tr[lid].cnt) * num; if(tr[Rr].cnt - tr[Lr].cnt <= num){ num -= tr[Rr].cnt - tr[Lr].cnt; return tr[Rr].tot - tr[Lr].tot + query(Ll, Rl, num); } else return query(Lr, Rr, num); } ll arr[100005]; ll solve(int n, int s, int d){ ll ans = 0; for(int i=1;i<=idx;i++) tr[i].l = tr[i].r = tr[i].tot = tr[i].cnt = 0; idx = 1; rt[0] = 1; for(int i=1;i<=n;i++) insert(rt[i-1], rt[i], arr[i], 0, 1000); for(int i=1;i<=s;i++){ if(d <= s-i) continue; ll tans = query(rt[i-1], rt[s], d - (s-i)); for(int j=s+1;j<=n;j++){ ll left = d - (s-i) - (j-i); if(left <= 0) break; ll que = query(rt[i-1], rt[j], left); tans = max(tans, que); } ans = max(ans, tans); } return ans; } ll findMaxAttraction(int n, int start, int d, int in[]) { start++; for(int i=1;i<=n;i++) arr[i] = in[i-1]; ll al = solve(n, start, d); reverse(arr+1, arr+1+n); start = n + 1 - start; ll ar = solve(n, start, d); return max(al, ar); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...