GCJ2012 Round 2 A : Swinging Wild

問題概要

問題文は状況を理解しにくいものになっているので、解答を見て問題を想像してください。

acceptされたコード

import std.stdio, std.algorithm;

int N, D;
int[] ds, ls;

void init(){
	scanf("%d", &N);
	ds = new int[N], ls = new int[N];
	foreach(i; 0..N){
		scanf("%d%d", &ds[i], &ls[i]);
	}
	scanf("%d", &D);
}

string solve(){
	auto dp = new int[N];
	dp[0] = ds[0];
	
	foreach(i; 0..N){
		if(ds[i] + dp[i] >= D){
			return "YES";
		}
		foreach(j; i+1..N)if(ds[j] <= ds[i] + dp[i]){
			dp[j] = max(dp[j], min(ds[j] - ds[i], ls[j]));
		}
	}
	
	return "NO";
}

void main(){
	int T;
	scanf("%d", &T);
	foreach(c; 0..T){
		init;
		writefln("Case #%d: %s", c+1, solve);
	}
}