hdu 1794


グリッド数
 
各0の方格が何個のs*sの中にあることを求めます
n=30で2000以上に達し、intを超えた場合
 
 
 
 
 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int map[31][31],a[10010];
struct op
{
	int num,count;
}p[31][31];
struct ed
{
	int x,y,cnt;
}e[1000];
int cmp(const void *a,const void *b)
{
	return *(int *)b-*(int *)a;
}
int amp(const void *a,const void *b)
{
	struct ed *c,*d;
	c=(ed *)a;
	d=(ed *)b;
	return d->cnt-c->cnt;
}
int MAX(int a,int b)
{
	if(a>b)return a;
	return b;
}
int main()
{
	int i,n,j,k,t,x,y,temp,m;
	__int64 sum;
	scanf("%d",&t);
	while(t--)
	{
		sum=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%d",&map[i][j]);
				p[i][j].num=n-MAX(i,j);// [i][j]          
				p[i][j].count=p[i][j].num;//[i][j]        
			}
		}
		scanf("%d",&m);
		for(i=0;i<m;i++)
			scanf("%d",&a[i]);
		qsort(a,m,sizeof(a[0]),cmp);
		for(i=0;i<n-1;i++)
		{
			for(j=0;j<n-1;j++)
			{
				x=i+1;y=j+1;temp=1;
				while(x<n&&y<n)// [i][j]    ,[x][y]      
				{
					p[x][y].count+=p[i][j].num-temp;
					k=x-1;
					while(k>=i)//i x-1    
					{
						p[k][y].count+=p[i][j].num-temp;
						k--;
					}
					k=y-1;
					while(k>=j)//j y-1   
					{
						p[x][k].count+=p[i][j].num-temp;
						k--;
					}
					x++;y++;//       1
					temp++;//                          1
				}
			}
		}
		k=0;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
				if(map[i][j]==0)
				{
					e[k].x=i;
					e[k].y=j;
					e[k++].cnt=p[i][j].count;
				}
		}
		qsort(e,k,sizeof(e[0]),amp);//           
		for(i=0;i<k;i++)
		{
			x=e[i].x;
			y=e[i].y;
			sum+=p[x][y].count*a[i];
		}
		printf("%I64d
",sum); } return 0; }