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); } }