제출 #116241

#제출 시각아이디문제언어결과실행 시간메모리
116241someone_aa휴가 (IOI14_holiday)C++17
24 / 100
99 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, result; int arr[maxn]; set<int>st; map<int,int>ind; int n, start, c; ll dp[maxn]; struct node { public: node *lc, *rc; ll cnt; ll sum; node(ll _cnt, ll _sum) { lc = rc = NULL; cnt = _cnt; sum = _sum; } node(node *a, node *b) { sum = a->sum + b->sum; cnt = a->cnt + b->cnt; lc = a; rc = b; } }; node* prefix[maxn]; node* build(int li=0, int ri=n) { if(li == ri) return new node(0LL, 0LL); else { int mid = (li + ri) / 2; return new node(build(li, mid), build(mid+1, ri)); } } node* update(node *curr, int pos, int sum_val, int li=0, int ri=n) { if(li == ri) { return new node(curr->cnt+1, curr->sum+sum_val); } else { int mid = (li + ri) / 2; if(pos <= mid) return new node(update(curr->lc, pos, sum_val, li, mid), curr->rc); else return new node(curr->lc, update(curr->rc, pos, sum_val, mid+1, ri)); } } ll solve(node *l, node *r, int k, int li=0, int ri=n) { if(k == 0) return 0LL; ll total_cnt = r->cnt - l->cnt; ll total_sum = r->sum - l->sum; //cout<<"["<<li<<" "<<ri<<"] -> "<<total_cnt<<", "<<total_sum<<"\n"; if(k == total_cnt) return total_sum; if(li == ri) return k * value[li]; else { int mid = (li + ri) / 2; ll total = r -> rc -> cnt - l -> rc -> cnt; ll sum_total = r -> rc -> sum - l -> rc -> sum; if(total >= k) return solve(l->rc, r->rc, k, mid+1, ri); else return sum_total + solve(l->lc, r->lc, k-total, li, mid); } } 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[mid-1], prefix[i], max(0LL, c - walk)); if(curr > dp[mid]) { dp[mid] = curr; optmid = i; } } result = max(result, dp[mid]); 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]]; } node *curr = build(); prefix[0] = curr; for(int i=1;i<=n;i++) { curr = update(curr, arr[i], value[arr[i]]); prefix[i] = curr; } solvedp(); return result; }

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

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...