Cod sursa(job #2487818)

Utilizator victorv88Veltan Victor victorv88 Data 5 noiembrie 2019 19:20:22
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;

unordered_map<int,int>fr;
unordered_map<int,int>combinari;

int n, x, mat[520][520], l1, l2, c1, c2, sp[520][520], a[12];

void citire()
{
    freopen("zone.in","r",stdin);
    scanf("%d",&n);
    for (int i=1; i<=9; ++i)
    {
        scanf("%d",&x);
        a[i]=x;
        fr[x]++;
    }

    for (int i=1; i<8; ++i)
    {
        for (int j=i+1; j<9; ++j)
        {
            for (int t=j+1; t<=10; ++t)
                combinari[a[i]+a[j]+a[t]]++;
        }
    }

    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=n; ++j)
        {
            scanf("%d",&mat[i][j]);
            sp[i][j]=sp[i-1][j]+mat[i][j];
        }
    }
}

void calculare_sume(int ind1, int ind2, int &s1, int &s2, int &s3)
{
    s1=s2=s3=0;
    for (int j=1; j<=ind1; ++j)
        s1+=sp[n][j];
    for (int j=ind1+1; j<=ind2; ++j)
        s2+=sp[n][j];
    for (int j=ind2+1; j<=n; ++j)
        s3+=sp[n][j];
}

bool verificare(int l1, int l2, int c1, int c2)
{
    int x[14];
    int ind=1;
    for (int i=1; i<=10; ++i)
        x[i]=0;
    for (int j=1; j<=c1; ++j)
    {
        x[ind]+=sp[l1][j];
    }
    ++ind;
    for (int j=c1+1; j<=c2; ++j)
    {
        x[ind]+=sp[l1][j];
    }
    ++ind;
    for (int j=c2+1; j<=n; ++j)
    {
        x[ind]+=sp[l1][j];
    }
    ++ind;


    for (int j=1; j<=c1; ++j)
    {
        x[ind]+=sp[l2][j]-sp[l1][j];
    }
    ++ind;
    for (int j=c1+1; j<=c2; ++j)
    {
        x[ind]+=sp[l2][j]-sp[l1][j];
    }
    ++ind;
    for (int j=c2+1; j<=n; ++j)
    {
        x[ind]+=sp[l2][j]-sp[l1][j];
    }
    ++ind;


    for (int j=1; j<=c1; ++j)
    {
        x[ind]+=sp[n][j]-sp[l2][j];
    }
    ++ind;
    for (int j=c1+1; j<=c2; ++j)
    {
        x[ind]+=sp[n][j]-sp[l2][j];
    }
    ++ind;
    for (int j=c2+1; j<=n; ++j)
    {
        x[ind]+=sp[n][j]-sp[l2][j];
    }
    ++ind;

    bool ok=true;
    for (int i=1; i<=9; ++i)
    {
        fr[x[i]]--;
        if (fr[x[i]]<0)
            ok=false;
    }
    for (int i=1; i<=9; ++i)
    {
        fr[x[i]]++;
    }

    return ok;
}

void impartire(int c1, int c2)
{
    int dif=n-1;
    for (int i=1; i<dif; ++i)
    {
        for (int j=i+1; j<=dif; ++j)
        {
            l1=i;
            l2=j;

            if (verificare(l1,l2,c1,c2))
            {
                printf("%d %d %d %d",l1,l2,c1,c2);
                exit(0);
            }
        }
    }
}

void solve()
{
    int dif=n-1;
    int s1, s2, s3;
    for (int i=1; i<dif; ++i)
    {
        for (int j=i+1; j<n; ++j)
        {
            c1=i;
            c2=j;

            calculare_sume(i,j,s1,s2,s3);

            if (combinari[s1] && combinari[s2] && combinari[s3])
            {
                impartire(i,j);
            }

        }
    }
}

int main()
{
    freopen("zone.out","w",stdout);
    citire();
    solve();
    return 0;
}