AOJ 2337: ねこ鍋改造計画（仮）

解法

cuteでソートするとDPできて、cuteの最大値が定数で、dp[鍋の種類][重さ] := max{cuteの最小値}となるようなテーブルがO(NW)で作れる。
できたテーブルは尺取法でO(W)で走査できる。全体で、O(NW)

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
#define fst first
#define snd second
#define chmax(X,Y) X=max(X,Y);
#define chmin(X,Y) X=min(X,Y);
#define N 1500
#define W 10010
int n[2], w, dp[2][W];
PP d[N];

int main(){
	cin>>n[0]>>n[1]>>w;
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < n[i]; j++){
			int a, b;
			cin>>a>>b;
			d[n[0]*i+j] = PP(b, P(a, i));
		}
	}
	sort(d, d+n[0]+n[1]);
	int res = 1000000000;
	for(int i = 0; i < n[0]+n[1]; i++){
		int b = d[i].fst, a = d[i].snd.fst, t = d[i].snd.snd;
		for(int j = w; j > a; j--)
			chmax(dp[t][j], dp[t][j-a]);
		dp[t][a] = b;
		int pos[2] = {};
		for(int j = 0; j < 2; j++) while(++pos[j]<=w && !dp[j][pos[j]]);
		while(pos[0]<=w && pos[1]<=w){
			int wf = abs(pos[1]-pos[0]), cf = max(b-dp[0][pos[0]], b-dp[1][pos[1]]);
			chmin(res, max(wf, cf));
			if(wf<=cf){
				int s = dp[0][pos[0]]>dp[1][pos[1]];
				int r = dp[s][pos[s]];
				while(++pos[s]<=w && dp[s][pos[s]]<=r);
			} else {
				int s = pos[0]>pos[1];
				while(++pos[s]<=w && !dp[s][pos[s]]);
			}
		}
	}
	cout<<res<<endl;

	return 0;
}