제출 #825066

#제출 시각아이디문제언어결과실행 시간메모리
825066Wael휴가 (IOI14_holiday)C++14
30 / 100
630 ms22732 KiB
#include<bits/stdc++.h> #include "holiday.h" //#include "grader.cpp" using namespace std; #define F first #define S second typedef long long ll; int const M = 1e5 + 10 , N = 30e5 + 10; int s[M] , cnt[N] , Left[N] , Right[N] , cur = 1 , L , R , k , Index; ll Size = (1 << 30) , ans , sum[N] , dp[M]; void Add(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) { if(i == 0) return; if(lx == rx) { sum[node] += lx; ++cnt[node]; return; } int mid = (lx + rx) / 2; if(i <= mid) { if(Left[node] == 0) Left[node] = ++cur; Add(i , Left[node] , lx , mid); } else { if(Right[node] == 0) Right[node] = ++cur; Add(i , Right[node] , mid + 1 , rx); } sum[node] = sum[Left[node]] + sum[Right[node]]; cnt[node] = cnt[Left[node]] + cnt[Right[node]]; } void Remove(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) { if(i == 0) return; if(lx == rx) { sum[node] -= lx; --cnt[node]; return; } ll mid = (lx + rx) / 2; if(i <= mid) { if(Left[node] == 0) Left[node] = ++cur; Remove(i , Left[node] , lx , mid); } else { if(Right[node] == 0) Right[node] = ++cur; Remove(i , Right[node] , mid + 1 , rx); } sum[node] = sum[Left[node]] + sum[Right[node]]; cnt[node] = cnt[Left[node]] + cnt[Right[node]]; } ll Get(ll need , ll node = 1 , ll lx = 1 , ll rx = Size) { //cout << need << " " << lx << endl; if(node == 0) return 0; if(need <= 0) return 0; if(lx == rx) return min(need , (ll)cnt[node]) * lx; ll mid = (lx + rx) / 2; if(cnt[Right[node]] >= need) { //cout << lx << " " << rx << " " << cnt[Right[node]] << endl; return Get(need , Right[node] , mid + 1 , rx); } else { need -= cnt[Right[node]]; return sum[Right[node]] + Get(need , Left[node] , lx , mid); } } void Move(int l , int r) { if(l > r) swap(l , r); while(L < l) { Remove(s[L]); ++L; } while(L > l) { --L; Add(s[L]); } while(R < r) { ++R; Add(s[R]); } while(R > r) { Remove(s[R]); --R; } } void Divide(int l , int r , int i , int j) { //cout << "in = " << l << " " << r << " " << i << " " << j << endl; if(i > j) return; int mid = (i + j) / 2; ll mx = 0 , Optimal = l; for(int I = l ; I <= r ; ++I) { Move(mid , I); //cout << sum[1] << endl; int d = k; d -= abs(mid - Index); d -= abs(mid - I); //cout << "d = " << d << endl; ll res = Get(d); if(res > mx) { mx = res; dp[mid] = res; Optimal = I; } } ans = max ( ans , mx ); //cout << "mid = " << mid << " " << dp[mid] << endl; Divide(l , Optimal , i , mid - 1); Divide(Optimal , r , mid + 1 , j); } long long int findMaxAttraction(int n, int start, int D , int attraction[]) { ++start; k = D; Index = start; for(int i = 1 ; i <= n ; ++i) s[i] = attraction[i - 1]; int d = D; for(int i = start ; i <= n ; ++i) { Add(s[i]); ans = max(ans , Get(d)); --d; } for(int i = start ; i <= n ; ++i) Remove(s[i]); d = D; for(int i = start ; i >= 1 ; --i) { Add(s[i]); ans = max(ans , Get(d)); --d; } for(int i = 1 ; i <= start ; ++i) Remove(s[i]); if(start > 1 && start < n) Divide(1 , start - 1 , start + 1 , n); if(start > 1 && start < n) Divide(start + 1 , n , 1 , start - 1 ); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...