hogloidのブログ

へなちょこ

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