PKU 2673 Kicc Wants to Move a Mountain!
http://poj.org/problem?id=2673
Kiccという人が山で一日t時間、毎時間xの土を掘る。
山の周囲にはm匹の猛獣がいて、猛獣iは最初に位置d_iにいて、掘る音を聞き続けている間は速さs_iで近づいていくる。
山に到達されると、一瞬で食べられるので、到達されるまえに休憩しないといけない。
休憩すると猛獣はもとの居場所に同じ速度で戻って行く。
このとい、Kiccが一日に掘ることのできる最大の土の量を求めろというような問題。
休憩や掘る時間は整数の範囲で取るものとする。
愚直にシミュレーションすると死ぬので、動物ごとに掘れる時間を計算し、その最小値をとれば良い。
0しかできないパターンの処理がうまくできてなくて1WA。
毎回思うのでうが、300問超えたあたりから、100問ごとの境を超えてしばらくは、微妙に解けなくなっている気がします。簡単な問題を探し当てたと思ってもTLEやWAにはまりまくって全然出来るきがしないです。
main(){ int t,x; cin>>t>>x; int m; cin>>m; int ans=t*x; rep(i,m){ int d,s; cin>>d>>s; if(d<=s){ ans=0; break; } int k=d/s; if(s*k==d)--k; int tans=k*x; tans+=(t-k)/2*x; ans=min(tans,ans); } cout<<ans<<endl; }