Cod sursa(job #3323095)

Utilizator mariusharabariMarius Harabari mariusharabari Data 16 noiembrie 2025 23:51:43
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.65 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("zone.in");
ofstream fout("zone.out");

long long mat[513][513], s[513][513], x, v[10], u[10];
int n, l1, l2, c1, c2;


int main(){
    ios_base::sync_with_stdio(0);
    fin.tie(NULL);
    fout.tie(NULL);

    fin>>n;
    for(int i=1;i<=9;i++)
        fin>>v[i];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            fin>>x;
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
        }
    }

    for(int l1=1;l1<=n-2;l1++){
        for(int c1=1;c1<=n-2;c1++){
            for(int s1=1;s1<=9;s1++)
                if(s[l1][c1]==v[s1]){
                    //cout<<1<<' '<<l1<<' '<<c1<<endl;
                    u[s1]=1;
                        for(int l2=l1+1;l2<n;l2++){
                            long long sum2=s[l2][c1]-s[l1][c1];
                            long long sum3=s[n][c1]-sum2-s[l1][c1];
                            for(int s2=1;s2<=9;s2++){
                                //cout<<sum2<<endl;
                                if(v[s2]==sum2&&u[s2]==0){
                                    //cout<<2<<' '<<l2<<' '<<c1<<endl;
                                    u[s2]=1;
                                    for(int s3=1;s3<=9;s3++){
                                        //cout<<sum3<<endl;
                                        if(v[s3]==sum3&&u[s3]==0){
                                            //cout<<3<<' '<<n<<' '<<c1<<endl;
                                            u[s3]=1;
                                            for(int c2=c1+1;c2<n;c2++){
                                                long long sum4=s[l1][c2]-s[l1][c1];
                                                for(int s4=1;s4<=9;s4++){
                                                    if(v[s4]==sum4&&u[s4]==0){
                                                        //cout<<4<<' '<<l1<<' '<<c2<<endl;
                                                        u[s4]=1;
                                                        long long sum5=s[l1][n]-sum4-s[l1][c1];
                                                        for(int s5=1;s5<=9;s5++){
                                                            if(v[s5]==sum5&&u[s5]==0){
                                                                //cout<<5<<' '<<l1<<' '<<n<<endl;
                                                                u[s5]=1;
                                                                long long sum6=s[l2][c2]-sum2-sum4-s[l1][c1];
                                                                for(int s6=1;s6<=9;s6++){
                                                                    if(v[s6]==sum6&&u[s6]==0){
                                                                        //cout<<6<<' '<<l2<<' '<<c2<<endl;
                                                                        u[s6]=1;
                                                                        long long sum7=s[n][c2]-sum3-sum6-sum2-sum4-s[l1][c1];
                                                                        for(int s7=1;s7<=9;s7++){
                                                                            if(v[s7]==sum7&&u[s7]==0){
                                                                                //cout<<7<<' '<<n<<' '<<c2<<endl;
                                                                                u[s7]=1;
                                                                                long long sum8=s[l2][n]-sum5-sum6-sum4-sum2-s[l1][c1];
                                                                                for(int s8=1;s8<=9;s8++){
                                                                                    if(v[s8]==sum8&&u[s8]==0){
                                                                                        //cout<<8<<' '<<l2<<' '<<n<<endl;
                                                                                        u[s8]=1;
                                                                                        fout<<l1<<' '<<l2<<' '<<c1<<' '<<c2<<'\n';
                                                                                        return 0;
                                                                                        u[s8]=0;
                                                                                    }
                                                                                }
                                                                                u[s7]=0;
                                                                            }
                                                                        }
                                                                        u[s6]=0;
                                                                    }
                                                                }
                                                                u[s5]=0;
                                                            }
                                                        }
                                                        u[s4]=0;
                                                    }
                                                }
                                            }
                                            u[s3]=0;
                                        }
                                    }
                                    u[s2]=0;
                                }
                            }
                        }
                    u[s1]=0;
                }
        }
    }
    return 0;
}