제출 #1252325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252325		PlayVoltz	커다란 상품 (IOI17_prize)	C++20	0 / 100	3 ms	2056 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<pii> ooga;

pii query(int a){
	if (ooga[a].fi!=-1)return ooga[a];
	vector<int> res=ask(a);
	if (!(res[0]+res[1]))throw a;
	return ooga[a]=mp(res[0], res[1]);
}

void dnc(int l, int r, int cl, int cr){
	if (l>r)return;
	int p1=(l+r)/2, p2=p1;
	while ((l<=p1<=r)||(l<=p2<=r)){
		if (l<=p1<=r){
			pii res=query(p1);
			if (res.fi>cl)dnc(l, p1-1, cl, res.se);
		}
		if (l<=p2<=r){
			pii res=query(p2);
			if (res.se>cr)dnc(p2+1, r, res.fi, cr);
		}
		--p1, ++p2;
	}
}

int find_best(int n){
	if (n==1)return 0;
	ooga.resize(n, mp(-1, -1));
	int id=0;
	for (int i=0, mx; i<sqrt(n)+30&&mx<27; ++i){
		pii res=query(i);
		if (res.fi+res.se>mx)mx=res.fi+res.se, id=i;
	}
	try{
		dnc(id, n-1, id, 0);
	}
	catch(int a){
		return a;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

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