Problem: Example

Input

2 5 4
5 7
4 8


Output

8 7

Solution (in CPP):

Solution:
// ACM-ICPCアジア地区予選2014 H. Cornering at Poles

#include <iostream>
#include <map>

using namespace std;

const long long INF = 1LL<<50;

int N;
map<long long, int> mem[2][150];
int r[150];
int s[150];
int lest[151];

int solve(int turn, int idx, long long diff);

int search(int turn, int idx, long long diff){
	if(idx == N) return 0;
	if(mem[turn][idx].empty()){
		int cur = solve(turn, idx, -INF/2);
		mem[turn][idx][-INF] = cur;
		long long key = -INF;
		while(true){
			long long L = key, R = INF/2;
			while(R-L>1){
				long long mid = (L+R)/2;
				if(solve(turn, idx, mid) == cur){
					L = mid;
				} else {
					R = mid;
				}
			}
			int next = solve(turn, idx, R);
			if(cur == next) break;
			mem[turn][idx][R] = next;
			cur = next;
			key = R;
		}
	}
	return (--mem[turn][idx].upper_bound(diff))->second;
}

int solve(int turn, int idx, long long diff){
	if(idx == N) return 0;
	int res = s[idx] + lest[idx+1] - search(!turn, idx+1, -(diff+r[idx]));
	if(diff > 0){
		res = max(res, search(turn, idx+1, diff-r[idx]-1));
	}
	return res;
}

int main(){
	int A, B;
	while(cin >> N >> A >> B){
		for(int i=0;i<N;i++) cin >> r[i] >> s[i];
		lest[N] = 0;
		for(int i=N-1;i>=0;i--) lest[i] = lest[i+1]+s[i];
		for(int i=0;i<N;i++){
			mem[0][i].clear();
			mem[1][i].clear();
		}
		int res = search(0, 0, A-B);
		cout << res << " " << lest[0]-res << endl;
	}
}