読者です 読者をやめる 読者になる 読者になる

Sweet War (AOJ1353)

A-Bにしかよらないのはまあわかる.A-Bは広い範囲の値を取るので,美味しみの方でメモりたくなる.dp[i][j]="i個目以降で(先手が)おいしみjを得るのに必要なエネルギー格差"を持って更新すればいいです.初め逆シミュレーションみたいなのをして頑張って更新をO(1)で出来ると思ったんだけどなんか合わなかったのでにぶたんした.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll dp[151][152],inf=1e18;
int N;
ll A,B,r[150],s[150];
int lef;
int geteasy(int i,ll x){
	return upper_bound(dp[i],dp[i]+151,x)-dp[i]-1;
}
int get(int i,ll x){
	int ret=0;
	chmax(ret,lef-geteasy(i+1,-x-r[i]));
	if(x>0){
		chmax(ret,geteasy(i+1,x-1-r[i]));
	}
	return ret;
}
int main(){
	int N;
	cin>>N>>A>>B;
	rep(i,N) cin>>r[i]>>s[i];
	rep(i,151) rep(j,152) dp[i][j]=inf;
	dp[N][0]=-inf;
	for(int i=N-1;i>=0;i--){
		lef+=s[i];
		rep(j,lef+1){
			ll ub=inf,lb=-inf;
			while(ub-lb>1){
				ll m=(ub+lb)/2;
				if(get(i,m)>=j) ub=m;
				else lb=m;
			}
			dp[i][j]=ub;
		}
	}
	ll x=geteasy(0,A-B);
	cout<<x<<" "<<lef-x<<endl;
}