Submission #467329

#TimeUsernameProblemLanguageResultExecution timeMemory
467329ivan_tudorHoliday (IOI14_holiday)C++14
100 / 100
2179 ms5752 KiB
#include"holiday.h" #include <vector> #include <iostream> #include <set> #include <algorithm> using namespace std; const int N = 100005; vector<int> a; multiset<int> big, small; long long sum; int canhold; int L, R; void insert_val(int v){ big.insert(v); sum += v; while((int)big.size() > max(canhold, 0)){ int lval = (*big.begin()); sum -= lval; big.erase(big.find(lval)); small.insert(lval); } } void erase_val(int v){ if(small.find(v) != small.end()){ small.erase(small.find(v)); } else if(big.find(v) != big.end()){ big.erase(big.find(v)); sum -= v; } while((int)big.size() < canhold && small.size() > 0){ int val = (*small.rbegin()); big.insert(val); sum += val; small.erase(small.find(val)); } } void transf(int newL, int newR){ while(L > newL){ canhold -=2; L--; insert_val(a[L]); } while(R < newR){ canhold --; R++; insert_val(a[R]); } while(L < newL){ canhold +=2; erase_val(a[L]); L++; } while(R > newR){ canhold++; erase_val(a[R]); R--; } } long long ans = 0; void solve(int l, int r, int opl, int opr){ if(r < l) return; int mid = (l + r)/2; transf(mid, opl); long long maxi = sum; int mpoz = opl; for(int i = opl; i <= opr; i++){ transf(mid, i); if(maxi < sum){ maxi = sum; mpoz = i; } } ans = max(ans, maxi); if(l == r) return; if(l <= mid - 1) solve(l, mid - 1, opl, mpoz); if(mid + 1 <= r) solve(mid + 1, r, mpoz, opr); } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { a = vector<int>(n); for(int i = 0; i < n; i++) a[i] = attraction[i]; big.clear(); small.clear(); big.insert(a[start]); sum = a[start]; L = R = start; canhold = d; solve(0, start, start, n - 1); reverse(a.begin(), a.end()); start = n - 1 - start; big.clear(); small.clear(); big.insert(a[start]); sum = a[start]; L = R = start; canhold = d; solve(0, start, start, n - 1); // cerr<<op; 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...