#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
vector<int> tab[200009];
vector<int> query(int a){
if(!tab[a].empty()){
return tab[a];
}
return tab[a] = ask(a);
}
int sumQuery(int a){
return query(a)[0]+query(a)[1];
}
int ans = -1, maxi = 0;
void solve(int l, int r, int nb, int ln){
if(nb == 0) return;
if(l > r) return ;
int a = r-l+1;
int cnt = 0;
int start = l;
int mem = ln;
for(int i = 1; i <= a; i++){
int curr = l+((a)/nb)*i;
if(curr > r) break;
if(sumQuery(curr) == 0){
ans = curr;
break;
}
if(sumQuery(curr) != maxi){
cnt++;
continue;
}
solve(start, curr-1, query(curr)[0]-mem, mem);
start = curr+1;
mem = query(curr)[0];
}
if(ans == -1 && cnt < nb && start <= r){
solve(start, r, query(r)[0]-mem, mem);
}
}
int find_best(int n)
{
for(int i = 1; i <= 1000; i++){
int curr = max(1,(n/1000))*i;
if(curr >= 0 && curr < n){
if(sumQuery(curr) == 0) return curr;
maxi = max(maxi, sumQuery(curr));
}
}
int start = 0;
int ln = 0;
for(int i = 1; i <= 1000; i++){
if(ans != -1) return ans;
int curr = max(1,(n/1000))*i;
if(curr >= 0 && curr < n){
solve(start, curr-1, query(curr)[0]-ln, ln);
start = curr+1;
ln = query(curr)[0];
}
}
if(ans == -1){
solve(start, n-1, maxi-ln,ln);
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1106 ms |
992368 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1139 ms |
1025868 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |