PKU 1928 The Peanuts
http://poj.org/problem?id=1928
シミュレーション
変な入力は無いと思うので、多分書けば普通に通るのだと思います。
#define F first #define S second main(){ int test; cin>>test; while(test--){ int m,n,k; cin>>m>>n>>k; map<int,PI> app; rep(i,m){ rep(j,n){ int t; cin>>t; if(t)app[t]=mp(i+1,j+1); } } map<int,PI>::iterator pp=app.end(); --pp; int cost=pp->second.first*2+1; if(cost>k){ cout<<0<<endl; continue; } int ans=pp->first; int x=pp->second.F,y=pp->S.S; cost=pp->second.F+1; while(pp!=app.begin()){ --pp; int tt=pp->F,nx=pp->S.F,ny=pp->S.S; if(cost+abs(nx-x)+abs(ny-y)+nx+1>k)break; ans+=tt; cost+=abs(nx-x)+abs(ny-y)+1; x=nx; y=ny; } cout<<ans<<endl; } }