Submission #1045379

#TimeUsernameProblemLanguageResultExecution timeMemory
1045379Trent커다란 상품 (IOI17_prize)C++17
96.04 / 100
40 ms1648 KiB
#include "prize.h" #include "bits/stdc++.h" using namespace std; #define forR(i, x) for(int i = 0; i < (x); ++i) #define REP(i, a, b) for(int i = (a); i < (b); ++i) struct pii{int a, b;}; typedef vector<int> vi; vi getVal(int i, map<int, vi>& cache) { if(cache.count(i)) return cache[i]; return cache[i] = ask(i); } void getBetter(int l, int r, int loid, int lOff, int rOff, map<int, vi>& cache) { assert(l <= r); int mid = (l + r) / 2; REP(ci, mid, r+1) { vi cv = getVal(ci, cache); if(cv[0] + cv[1] == loid) { if(cv[0] + lOff > 0) getBetter(l, ci - 1, loid, lOff, -cv[1], cache); if(cv[1] + rOff > 0) getBetter(ci+1, r, loid, -cv[0], rOff, cache); return; } } for(int ci = mid - 1; ci >= l; --ci) { vi cv = getVal(ci, cache); if(cv[0] + cv[1] == loid) { if(cv[0] + lOff > 0) getBetter(l, ci - 1, loid, lOff, -cv[1], cache); if(cv[1] + rOff > 0) getBetter(ci+1, r, loid, -cv[0], rOff, cache); return; } } } const int MV = 500; int find_best(int n){ map<int, vi> ca; forR(i, min(n, MV)) getVal(i, ca); int loVal = ca[0][0] + ca[0][1]; forR(i, min(n, MV)) loVal = max(loVal, ca[i][0] + ca[i][1]); getBetter(0, n-1, loVal, 0, 0, ca); int bi = -1; for(auto [ci, cv] : ca) if(cv[0] + cv[1] == 0) { bi = ci; } assert(bi != -1); return bi; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...