Sgu/167

/by Logic
#include<stdio.h>
#include<string.h>
const int maxn=17;
int n,m,k,te[maxn][maxn]={0},ans=-1,la=0;
int oc[maxn][3],lin=0;
int f[maxn][maxn][maxn][maxn*maxn][4]={0};
int fr[maxn][maxn][maxn][maxn*maxn][4]={0};
int ch[4][5]={{4,0,1,2,3},{2,1,3},{2,2,3},{1,3}};
inline int max(int xx,int yy) {return xx>yy?xx:yy;}
inline int hash(int i,int l,int r,int t,int j) {return j*3200000+t*8000+i*400+l*20+r;}
void get(int l,int r,int st,int &lowl,int &higl,int &lowr,int &higr)
{
	switch(st)
	{
		case 0: lowl=1,higl=l,lowr=r,higr=m;
				break;
		case 1: lowl=l,higl=r,lowr=r,higr=m;
				break;
		case 2: lowl=1,higl=l,lowr=l,higr=r;
				break;
		case 3: lowl=l,higl=m,lowr=1,higr=r;
				break;
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
#endif
	int i,j,l,r,t,d,l0,r0;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			scanf("%d",&te[i][j]);
			te[i][j]+=te[i][j-1];
		}
	memset(f,-1,sizeof(f));
	for(i=1;i<=n;i++)
		for(l=1;l<=m;l++)
			for(r=l;r<=m;r++)
				f[i][l][r][r-l+1][0]=te[i][r]-te[i][l-1];
	for(i=1;i<=n;i++)
		for(l=1;l<=m;l++)
			for(r=l;r<=m;r++)
				for(t=r-l+1;t<k;t++)
					for(j=0;j<4;j++)
						if(i<n&&f[i][l][r][t][j]>=0)
						{
							for(d=1;d<=ch[j][0];d++)
							{
								int lowl,higl,lowr,higr;
								get(l,r,ch[j][d],lowl,higl,lowr,higr);
								for(l0=lowl;l0<=higl;l0++)
									for(r0=max(l0,lowr);r0<=higr;r0++)
									{
										int tmp=f[i][l][r][t][j]+te[i+1][r0]-te[i+1][l0-1],&now=f[i+1][l0][r0][t+r0-l0+1][ch[j][d]];
										if(t+r0-l0+1<=k&&tmp>now)
											now=tmp,fr[i+1][l0][r0][t+r0-l0+1][ch[j][d]]=hash(i,l,r,t,j);
									}
							}
						}
	for(i=1;i<=n;i++)
		for(l=1;l<=m;l++)
			for(r=l;r<=m;r++)
				for(j=0;j<4;j++)
					if(ans<f[i][l][r][k][j])
						ans=f[i][l][r][k][j],la=hash(i,l,r,k,j);
	printf("Oil : %d\n",max(ans,0));
	for(;la;la=fr[i][l][r][t][j])
	{
		j=la/3200000,la%=3200000;
		t=la/8000,la%=8000;
		i=la/400,la%=400;
		l=la/20,la%=20;
		r=la;
		//printf("%d %d %d %d %d    %d\n",i,l,r,t,j,fr[i][l][r][t][j]);
		oc[lin][0]=i,oc[lin][1]=l,oc[lin][2]=r;
		lin++;
	}
	for(i=lin-1;i>=0;i--)
		for(j=oc[i][1];j<=oc[i][2];j++)
			printf("%d %d\n",oc[i][0],j);
	return 0;
}