Submission #297900

#	Time	Username	Problem	Language	Result	Execution time	Memory
297900		Batyr	The Big Prize (IOI17_prize)	C++17	0 / 100	96 ms	1384 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define pii pair<int,int>
#define mkp make_pair

const int maxn=2e5+5;
pii dp[maxn];

// vector<int> ask(int nd){
//     return {1,2};
// }

pii f(int l,int r){
    if(dp[l] == mkp(0,0)){
        vector<int>p = ask(l);
        dp[l].ff=p[0];
        dp[l].ss=p[1];
    }
    if(dp[r] == mkp(0,0)){
        vector<int> p = ask(r);
        dp[r].ff=p[0];
        dp[r].ss=p[1];
    }
    if(dp[l].ff+dp[l].ss == dp[r].ff+dp[r].ss and dp[l].ss - dp[r].ss == 0) return {dp[l].ff + dp[l].ss,l};
    pii cep=f(l,(l+r)/2);
    pii sag=f((l+r)/2,r);
    if(cep.ff < sag.ff) return cep;
    return sag;
}

int find_best(int n){
    return f(0,n-1).ss;
}

// int main() {
    
//     cout<< find_best(4);
// }

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80