一道消磨人的题，自己手画一下状态就好了。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#define gc getchar()
using namespace std;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[16][226][16][16][2][2],a[16][16],b[16][16];
int pl[16][226][16][16][2][2],pr[16][226][16][16][2][2];
int px[16][226][16][16][2][2],py[16][226][16][16][2][2];
void update(int val,int i,int j,int l,int r,int x,int y,int L,int R,int X,int Y)
{
    if(f[i][j][l][r][x][y]>=val)return ;
    f[i][j][l][r][x][y]=val;
    pl[i][j][l][r][x][y]=L;pr[i][j][l][r][x][y]=R;
    px[i][j][l][r][x][y]=X;py[i][j][l][r][x][y]=Y;
}
void pri(int i,int j,int l,int r,int x,int y)
{
    if(!j)return ;
    pri(i-1,j-(r-l+1),pl[i][j][l][r][x][y],pr[i][j][l][r][x][y],px[i][j][l][r][x][y],py[i][j][l][r][x][y]);
    for(int k=l;k<=r;k++)printf("%d %d\n",i,k);
}
int main()
{
    int n,m,t;qr(n),qr(m),qr(t);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            qr(a[i][j]);
            b[i][j]=b[i][j-1]+a[i][j];
        }
    memset(f,0xcf,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=t;j++)
            for(int l=1;l<=m;l++)
                for(int r=l;r<=m;r++)
                {
                    int k=r-l+1;if(k>j)break;
                    int now=b[i][r]-b[i][l-1];
                    if(k==j)
                        for(int x=0;x<2;x++)
                            for(int y=0;y<2;y++)
                                update(now,i,j,l,r,x,y,m,0,x,y);
                    else
                    {
                        for(int p=l;p<=r;p++)
                            for(int q=p;q<=r;q++)
                                update(f[i-1][j-k][p][q][1][0]+now,i,j,l,r,1,0,p,q,1,0);//1表示递减，0表示递增
                            for(int p=l;p<=r;p++)
                                for(int q=r;q<=m;q++)
                                    for(int y=0;y<2;y++)
                                        update(f[i-1][j-k][p][q][1][y]+now,i,j,l,r,1,1,p,q,1,y);
                            for(int p=1;p<=l;p++)
                                for(int q=l;q<=r;q++)
                                    for(int x=0;x<2;x++)
                                        update(f[i-1][j-k][p][q][x][0]+now,i,j,l,r,0,0,p,q,x,0);
                            for(int p=1;p<=l;p++)
                                for(int q=r;q<=m;q++)
                                    for(int x=0;x<2;x++)
                                        for(int y=0;y<2;y++)
                                            update(f[i-1][j-k][p][q][x][y]+now,i,j,l,r,0,1,p,q,x,y);
                    }
                }
    int ans=0,ansi,ansl,ansr,ansx,ansy;
    for(int i=1;i<=n;i++)
        for(int l=1;l<=m;l++)
            for(int r=l;r<=m;r++)
                for(int x=0;x<2;x++)
                    for(int y=0;y<2;y++)
                        if(ans<f[i][t][l][r][x][y])
                        {
                            ans=f[i][t][l][r][x][y];
                            ansi=i,ansl=l,ansr=r,ansx=x,ansy=y;
                        }
    printf("Oil : %d\n", ans);
    pri(ansi,t,ansl,ansr,ansx,ansy);
    return 0;
}