Submission #1155683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155683		yellowtoad	The Big Prize (IOI17_prize)	C++20	20 / 100	26 ms	5368 KiB

prize

#include <iostream>
#include <vector>
using namespace std;

std::vector<int> ask(int i);

vector<int> res, dp[200010];
int ans, maxx, cnt;

void solve(int l, int r) {
	if (l > r) return;
	if (dp[l-1] == dp[r+1]) return;
	int mid = (l+r)/2, ll, rr;
	dp[mid] = ask(mid-1);
	if (dp[mid][0]+dp[mid][1] == 0) ans = mid-1;
	if (dp[mid][0]+dp[mid][1] == maxx) {
		solve(l,mid-1);
		solve(mid+1,r);
	} else {
		ll = mid-1;
		while (ll >= l) {
			dp[ll] = ask(ll-1);
			if (dp[ll][0]+dp[ll][1] == 0) ans = ll-1;
			if (dp[ll][0]+dp[ll][1] == maxx) break;
			ll--;
		}
		solve(l,ll-1);
		rr = mid+1;
		while (rr <= r) {
			dp[rr] = ask(rr-1);
			if (dp[rr][0]+dp[rr][1] == 0) ans = rr-1;
			if (dp[rr][0]+dp[rr][1] == maxx) break;
			rr++;
		}
		solve(rr+1,r);
	}
}

int find_best(int n) {
	for (int i = 0; i < min(450,n); i++) {
		res = ask(i);
		maxx = max(maxx,res[0]+res[1]);
	}
	dp[0] = {0,maxx};
	dp[n+1] = {maxx,0};
	solve(1,n);
	return ans;
}

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