AOJ 0574: Nails

最大値の伝播です。正方形型にメモリを確保してしまうと、半分くらい無駄になってMLEしてしまうので、三角形にします。

(こんな感じに)

(-1, 0)
( 0, 0) ( 0, 1)
( 1, 0) ( 1, 1) ( 1, 2)
( 2, 0) ( 2, 1) ( 2, 2) ( 2, 3)
...

この図で、輪ゴムにかかる可能性があるマスは( 1, 1), ( 2, 1), ( 2, 2)で、見向きもされないマスは(-1, 0)です。また、( x, y)は0-indexedで( (x+1)(x+2)/2 + y )番目です。

#include <cstdio>
#include <algorithm>
using namespace std;

int m,n,tr[12512502],x,y,s,ans;//f(5000,5000) == 12512501

int f(int i, int j){
	return (i+1)*(i+2)/2+j;
}

int main(){
	scanf("%d%d",&n,&m);
	
	for(int i = 0; i < m; i++){
		scanf("%d%d%d",&x,&y,&s);
		tr[f(x,y)] = s+1;
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= i; j++){
			if(tr[f(i,j)] = max(tr[f(i,j)],max(tr[f(i-1,j)],tr[f(i-1,j-1)])-1)){
				ans++;
			}
		}
	}
	
	printf("%d\n",ans);
	return 0;
}