记录编号	115	评测结果	AWWWWWWWEE
题目名称	[FZYZOJ 1273] 坦克游戏	最终得分	10
用户昵称	BYVoid	是否通过	未通过
代码语言	C++	运行时间	0.117 s
提交时间	2008-04-23 18:04:56	内存使用	11.73 MiB

#include <iostream>
#include <fstream>
#define MAXR 101
#define MAX 1001

using namespace std;

typedef struct
{
	int x,y;
	long v;
}point;

class heap
{
private:
	point *hp;
public:
	long size;
	~heap()
	{
		free(hp);
	}
	heap()
	{
		size=0;
		hp=(point *)malloc(sizeof(point)*MAX*MAX);
		hp[0].v=0x7FFFFFF;
	}
	point del()
	{
		long i,child;
		point rtnv=hp[1],mv=hp[size];
		size--;
		for (i=1;i*2<=size;i=child)
		{
			child=i*2;
			if (child!=size)
				if (hp[child+1].v>hp[child].v)
					child++;
			if (mv.v<hp[child].v)
				hp[i]=hp[child];
			else
				break;
		}
		hp[i]=mv;
		return rtnv;
	}
	void ins(point k)
	{
		long i;
		size++;
		for (i=size;hp[i/2].v<k.v;i/=2)
			hp[i]=hp[i/2];
		hp[i]=k;
	}
};


ifstream fi("gametk.in");
ofstream fo("gametk.out");
long N,M,R,T,max_s=0;
point sq[MAX][MAX];
heap *H;


void init()
{
	long i,j;
	fi >> N >> M >> R >> T;
	H=new heap();
	for (i=1;i<=N;i++)
		for (j=1;j<=M;j++)
		{
			fi >> sq[i+R][j+R].v;
			sq[i+R][j+R].x=i+R;
			sq[i+R][j+R].y=j+R;
			if (i<=R && j<=R)
				H->ins(sq[i+R][j+R]);
		}
}

bool inr(point P,long x,long y)
{
	return P.x>=x-R && P.x<=x+R && P.y>=y-R && P.y<=y+R;
}

void cs()
{
	long i,j,k,t,S,cnt;
	point g[MAXR];
	for (i=1+R;i<=N;i++)
	{
		for (j=1+R;j<=M;j++)
		{
			t=T-(i+j-2-R-R);
			cnt=0;
			S=0;
			for (k=1;k<=t;k++)
			{
				while ( !inr( (g[k]=H->del()),i,j ) && H->size>0);
				S+=g[k].v;
				cnt++;
				if (g[k].v==0 || H->size==0)
					break;
			}
			if (S>max_s)
				max_s=S;
			for (k=1;k<=cnt;k++)
				H->ins(g[k]);

			if (j<M)
				for (k=i-R;k<=i+R;k++)
				{
					if (sq[k][j+R+1].v>0)
						H->ins(sq[k][j+R+1]);
				}
		}
		if (i<N)
			for (k=1+R;k<=M;k++)
			{
				if (sq[i+R+1][k].v>0)
					H->ins(sq[i+R+1][k]);
			}
	}
}

void print()
{
	fo << max_s;
	fi.close();
	fo.close();
}

int main()
{
	init();
	cs();
	print();
	return 0;
}