Cod sursa(job #2482274)

Utilizator stan_flaviusStan Flavius Stefan stan_flavius Data 27 octombrie 2019 23:22:49
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 513

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

int n;
int mat[nmax][nmax];
vector<long long> sume;
long long mat_sum_part[nmax][nmax];

long long det_sum_part(int l1,int c1,int l2,int c2)
{
    return mat_sum_part[l2][c2]-mat_sum_part[l2][c1-1]-mat_sum_part[l1-1][c2]+mat_sum_part[l1-1][c1-1];
}

bool caut_sum(long long sum)
{
    for(int i=0; i<9; i++)
        if(sum==sume[i]) return 1;
    return 0;
}

bool verif(int l1,int c1,int l2,int c2)
{
    vector<long long>sume_int;
    sume_int.push_back(det_sum_part(1,1,l1,c1));
    sume_int.push_back(det_sum_part(1,c1+1,l1,c2));
    sume_int.push_back(det_sum_part(1,c2+1,l1,n));
    sume_int.push_back(det_sum_part(l1+1,1,l2,c1));
    sume_int.push_back(det_sum_part(l1+1,c1+1,l2,c2));
    sume_int.push_back(det_sum_part(l1+1,c2+1,l2,n));
    sume_int.push_back(det_sum_part(l2+1,1,n,c1));
    sume_int.push_back(det_sum_part(l2+1,c1+1,n,c2));
    sume_int.push_back(det_sum_part(l2+1,c2+1,n,n));
    sort(sume_int.begin(),sume_int.end());
    if(sume_int==sume) return 1;
    return 0;
}

int main()
{
    fin>>n;
    for(int i=1; i<=9; i++)
        {
            long long x;
            fin>>x;
            sume.push_back(x);
        }
    sort(sume.begin(),sume.end());

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            fin>>mat[i][j];

    for(int i=0; i<=n+1; i++)
         mat_sum_part[0][i]=mat_sum_part[n+1][i]=0;
    for(int i=0; i<=n+1; i++)
         mat_sum_part[i][0]=mat_sum_part[i][n+1]=0;
    for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                {
                    mat_sum_part[i][j]=mat[i][j]+mat_sum_part[i-1][j]+mat_sum_part[i][j-1]-mat_sum_part[i-1][j-1];
                }
        }

    for(int l1=1; l1<n; l1++)
        {
            for(int c1=1; c1<n; c1++)
                {
                    long long sum_1=det_sum_part(1,1,l1,c1);
                    if(caut_sum(sum_1))
                        {
                            for(int l2=l1+1; l2<n; l2++)
                                {
                                    long long sum_2=det_sum_part(l1+1,1,l2,c1);
                                    if(caut_sum(sum_2))
                                        {
                                            for(int c2=c1+1; c2<n; c2++)
                                                {
                                                    //fout<<l1<<" "<<l2<<" "<<c1<<" "<<c2<<"\n";
                                                    if(verif(l1,c1,l2,c2))
                                                        {
                                                            fout<<l1<<" "<<l2<<" "<<c1<<" "<<c2;
                                                            return 0;
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
    return 0;
}