求调 90pts WA on#4 悬一关

#include <bits/stdc++.h>
using namespace std;
const int INF=-1e9;
int N,M,K,Ans,sum[16][16],dp[16][401][16][16][2][2];
struct Node{
    int h,l,r,an1,an2,q,ans;
}pre[16][401][16][16][2][2];
void print(Node x){
    if(x.h==0)return;
    print(pre[x.h][x.q][x.l][x.r][x.an1][x.an2]);
    for(int i=x.l;i<=x.r;i++)cout<<x.h<<" "<<i<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>K;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            int x;cin>>x;
            sum[i][j]=sum[i][j-1]+x;
        }
    }
    for(int j=0;j<=K;j++){
        for(int l=1;l<=M;l++){
            for(int r=l;r<=M;r++){
                for(int p=0;p<2;p++){
                    for(int q=0;q<2;q++){
                        dp[0][j][l][r][p][q]=(j==0)?0:INF;
                    }
                }
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<=K;j++){
            for(int l=1;l<=M;l++){
                for(int r=l;r<=M;r++){
                    for(int p=0;p<2;p++){
                        for(int q=0;q<2;q++){
                            dp[i][j][l][r][p][q]=INF;
                        }
                    }
                }
            }
        }
        for(int l=1;l<=M;l++){
            for(int r=l;r<=M;r++){
                int t=r-l+1,tt=sum[i][r]-sum[i][l-1];
                for(int j=t;j<=K;j++){
                    for(int ll=l;ll<=r;ll++){
                        for(int rr=ll;rr<=r;rr++){
                            int tmp=dp[i-1][j-t][ll][rr][0][0]+tt;
                            if(tmp>dp[i][j][l][r][0][0]){
                                dp[i][j][l][r][0][0]=tmp;
                                pre[i][j][l][r][0][0]={i-1,ll,rr,0,0,j-t,dp[i-1][j-t][ll][rr][0][0]};
                            }
                        }
                    }
                    for(int ll=l;ll<=r;ll++){
                        for(int rr=r;rr<=M;rr++){
                            for(int qq=0;qq<=1;qq++){
                                int tmp=dp[i-1][j-t][ll][rr][0][qq]+tt;
                                if(tmp>dp[i][j][l][r][0][1]){
                                    dp[i][j][l][r][0][1]=tmp;
                                    pre[i][j][l][r][0][1]={i-1,ll,rr,0,qq,j-t,dp[i-1][j-t][ll][rr][0][qq]};
                                }
                            }
                        }
                    }
                    for(int ll=1;ll<=l;ll++){
                        for(int rr=l;rr<=r;rr++){
                            for(int pp=0;pp<=1;pp++){
                                int tmp=dp[i-1][j-t][ll][rr][pp][0]+tt;
                                if(tmp>dp[i][j][l][r][1][0]){
                                    dp[i][j][l][r][1][0]=tmp;
                                    pre[i][j][l][r][1][0]={i-1,ll,rr,pp,0,j-t,dp[i-1][j-t][ll][rr][pp][0]};
                                }
                            }
                        }
                    }
                    for(int ll=1;ll<=l;ll++){
                        for(int rr=r;rr<=M;rr++){
                            for(int pp=0;pp<=1;pp++){
                                for(int qq=0;qq<=1;qq++){
                                    int tmp=dp[i-1][j-t][ll][rr][pp][qq]+tt;
                                    if(tmp>dp[i][j][l][r][1][1]){
                                        dp[i][j][l][r][1][1]=tmp;
                                        pre[i][j][l][r][1][1]={i-1,ll,rr,pp,qq,j-t,dp[i-1][j-t][ll][rr][pp][qq]};
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    Ans=INF;
    int hi=0,li=0,ri=0,px=0,py=0;
    for(int i=1;i<=N;i++){
        for(int j=0;j<=K;j++){
            for(int l=1;l<=M;l++){
                for(int r=l;r<=M;r++){
                    for(int p=0;p<2;p++){
                        for(int q=0;q<2;q++){
                            if(dp[i][j][l][r][p][q]>Ans){
                                Ans=dp[i][j][l][r][p][q];
                                hi=i;li=l;ri=r;px=p;py=q;
                            }
                        }
                    }
                }
            }
        }
    }
    if(K==0)Ans=0;
    cout<<"Oil : "<<Ans<<endl;
    if(K>0){
        pre[0][0][0][0][0][0]={hi,li,ri,px,py,K,Ans};
        print(pre[0][0][0][0][0][0]);
    }
    return 0;
}