Problem: Example

Input

2 5 4
5 7
4 8


Output

8 7

Solution (in CPP):

Solution:
#include<cstdio>
#include<algorithm>

using namespace std;

const long long inf=1e12;

int N;
int A,B;
int r[155],s[155];
int Sum;

long long f[155][2][155];

int get(int i,int p,long long x){
	int res=0;
	for(int S=0;S<=Sum;S++){
		if(f[i][p][S]<=x){
			res=S;
		}
	}
	return res;
}

int simulate(int i,int p,long long x){
	if(p==0){
		int res=get(i+1,1,x+r[i])+s[i];
		if(x>0){
			int tmp=get(i+1,0,x-1-r[i]);
			res=max(res,tmp);
		}
		return res;
	}else{
		int res=get(i+1,0,x-r[i]);
		if(x<0){
			int tmp=get(i+1,1,x+1+r[i])+s[i];
			res=min(res,tmp);
		}
		return res;
	}
}

int main(){
	scanf("%d%d%d",&N,&A,&B);
	for(int i=0;i<N;i++){
		scanf("%d%d",r+i,s+i);
		Sum+=s[i];
	}
	for(int i=0;i<N;i++) for(int j=0;j<2;j++){
		for(int k=0;k<=Sum;k++){
			f[i][j][k]=inf;
		}
	}
	f[N-1][0][s[N-1]]=-inf;
	f[N-1][1][0]=-inf;
	for(int i=N-2;i>=0;i--){
		for(int j=0;j<=1;j++){
			for(int s=0;s<=Sum;s++){
				long long lb=-inf/2,ub=inf/2;
				while(ub-lb>1){
					long long x=(ub+lb)/2;
					int val=simulate(i,j,x);
					if(val>=s){
						ub=x;
					}else{
						lb=x;
					}
				}
				if(ub==(-inf/2)+1) f[i][j][s]=-inf;
				else if(ub==(inf/2)) f[i][j][s]=inf;
				else f[i][j][s]=ub;
			}
		}
	}
	int ans=0;
	for(int i=0;i<=Sum;i++){
		if(f[0][0][i]<=A-B){
			ans=i;
		}
	}
	printf("%d %d\n",ans,Sum-ans);
	return 0;
}