제출 #297972

#제출 시각아이디문제언어결과실행 시간메모리
297972Batyr커다란 상품 (IOI17_prize)C++17
90 / 100
91 ms2816 KiB
#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> const int maxn=2e5+5; int dp[maxn][3]; //~ vector<int> ask(int pos){ //~ cout<<pos<<'\n'; //~ int a,b; //~ cin >> a >> b; //~ return {a,b}; //} pii f(int l,int r){ //~ cout<<l<<' '<<r<<'\n'; 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]==0) return {0,l}; if(dp[r][0]+dp[r][1]==0) return {0,r}; if(dp[l][0]+dp[l][1] == dp[r][0]+dp[r][1] and dp[r][0]-dp[l][0]==0) return {dp[r][0]+dp[r][1],r}; pii cep = f(l,(l+r)/2); pii sag = f((l+r)/2+1,r); if(cep.ff < sag.ff) return cep; return sag; } int find_best(int n){ memset(dp,-1,sizeof(dp)); pii p = f(0,n-1); return p.ss; } //~ int main(){ //~ int n; //~ cin >> n; //~ cout << find_best(n); //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...