# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1214572 | exoworldgd | The Big Prize (IOI17_prize) | C++20 | 0 ms | 0 KiB |
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
map<int,vector<int>> mp;
vector<int> q(int pos) {
if (mp.count(pos)) return mp[pos];
return mp[pos] = ask(pos);
}
int find_best(int n) {
mp.clear();
int mx = 0, pos = 0;
for (int i = 0; i < min(n,500); i++) {
vector<int> res = q(i);
if (res[0]+res[1] == 0) return i;
mx = max(mx,res[0]+res[1]);
}
while (pos < n) {
vector<int> res = query(pos);
if (res[0]+res[1] == 0) return pos;
if (res[0]+res[1] == mx) pos = res[0]+1;
else pos++;
}
return 0;
}