Submission #297906

#	Time	Username	Problem	Language	Result	Execution time	Memory
297906		Batyr	The Big Prize (IOI17_prize)	C++17	0 / 100	1 ms	384 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;
int dp[maxn][3];

pii f(int l,int r){
    if(dp[l][0]==-1 and dp[l][1] == -1 ){
        vector<int>p = ask(l);
        dp[l][0]=p[0];
        dp[l][1]=p[1];
    }

    if(dp[r][0] == -1 and dp[r][1] == -1){
        vector<int> p = ask(r);
        dp[r][0]=p[0];
        dp[r][1]=p[1];
    }
    if(dp[l][0]+dp[l][1] == dp[r][0]+dp[r][1] and dp[l][1] - dp[r][1] == 0) return {dp[l][0] + dp[l][1],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