JOI 合宿 Pyramid
DPでし。高い所からゴリゴリやります。
priority_queue使っても面白そうですがlogの分だけTimeLimitが危なそう
vvi buf; vector<vp> top; int w,h,n; int main(){ FILE* fp=fopen("out.txt","w"); top.resize(3001); scanf("%d%d%d",&w,&h,&n); buf.resize(h,vi(w,0)); REP(i,n){ int a,b,c;scanf("%d%d%d",&a,&b,&c); buf[b][a]=max(buf[b][a],c); top[c].pb(mp(b,a)); } lint res=0; int maxi=0; for(int i=3000;i>=1;--i){ REP(j,top[i].size()){ pi p=top[i][j]; if(buf[p.fr][p.sc]>i) continue; REPN(k,2,-1) REPN(l,2,-1){ if(k==0 && l==0) continue; int px=p.sc+l,py=p.fr+k; if(px<0 || py<0 || px>=w || py>=h || buf[py][px]>=buf[p.fr][p.sc]-1) continue; top[i-1].pb(mp(py,px)); buf[py][px]=buf[p.fr][p.sc]-1; } } } REP(i,h)REP(j,w) res+=buf[i][j]; fprintf(fp,"%lld\n",res); return 0; }