Submission #131146

#	Time	Username	Problem	Language	Result	Execution time	Memory
131146		amiratou	The Big Prize (IOI17_prize)	C++14	0 / 100	104 ms	5328 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> dp[200002];
bool check(int med,int idx){
	vector<int> res;
	if(!dp[med].empty())res=dp[med];
	else res=ask(med),dp[med]=res;
	return (dp[idx][0]+dp[idx][1])<(res[0]+res[1]);
}
int find_best(int n) {
	int maxi,idx=0;
	for (int i = 0; i < min(450,n); ++i)
	{
		dp[i]=ask(i);
		if(dp[i][0]+dp[i][1]==0)return i;
		if(dp[i][0]+dp[i][1]>=maxi)maxi=dp[i][0]+dp[i][1],idx=i;
	}
	while(idx<n){
		int l=idx+1,r=n-1,ans=idx+1;
		//cerr<<ans<<"\n";
		while(l<=r){
			int med=(l+r)/2;
			if(check(med,idx))ans=med,l=med+1;
			else r=med-1;
			if(dp[med][0]+dp[med][1]==0)return med;
		}
		while(ans<n){
			vector<int> res;
			if(!dp[ans].empty())res=dp[ans];
			else res=ask(ans),dp[ans]=res;
			if(dp[ans][0]+dp[ans][1]==0)return ans;
			if(dp[ans][0]+dp[ans][1]>maxi){
				maxi=dp[ans][0]+dp[ans][1],idx=ans;
				break;
			}
			ans++;
		}
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:17:3: warning: 'maxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(dp[i][0]+dp[i][1]>=maxi)maxi=dp[i][0]+dp[i][1],idx=i;
   ^~

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