Cod sursa(job #2536682)

Utilizator WladDalwMvladutu cristian vlad WladDalwM Data 2 februarie 2020 15:04:58
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("zone.in");
ofstream cout("zone.out");

long long mat[520][520];
long long S[10];
long long Sv[10];
int r[5] = {513,513, 513, 513 ,513};

int main()
{
    long long n , s1 , s2 , s3, i1, i2, i3 , i , j , l1 , l2, c1 , c2 , pas;
    bool ok;
    cin >> n;
    for(i = 1; i <= 9; i++)
        cin >> S[i];
    sort(S + 1, S + 10);
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
            {cin >> mat[i][j];
                mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
            }
    }
    for(l1 = 1; l1 <= n; l1++)
    {
        for(i1 = 1; i1 <= 9; i1++)
        {
            s1 = S[i1];
            for(i2 = 1; i2 <= 9; i2++)
            {
                s2 = S[i2];
                for(i3 = 1; i3 <= 9; i3++)
                {
                    s3 = S[i3];
                    ok = true;
                    ///  c1
                    c1 = 1;
                    pas = 512;
                    while(pas)
                    {
                        if(c1 + pas <= n - 2)
                           if(mat[l1][c1 + pas] <= s1)
                            c1 += pas;
                    pas /= 2;
                    }
                    if(mat[l1][c1] != s1)
                        ok = false;
                    else
                    { ///***

                    /// c2
                    c2 = c1 + 1;
                    pas = 512;
                    while(pas)
                    {
                        if(c2 + pas <= n - 1)
                            if(mat[l1][c2 + pas] - mat[l1][c1] <= s2)
                                c2 += pas;
                        pas /= 2;
                    }
                    if(mat[l1][c2] - mat[l1][c1] != s2)
                        ok = false;
                    else
                    {///***

                    /// l2
                    l2 = l1 + 1;
                    pas = 512;
                    while(pas)
                    {
                        if(l2 + pas <= n - 1)
                            if(mat[l2 + pas][c1] - mat[l1][c1] <= s3)
                                l2 += pas;
                        pas /= 2;
                    }
                    if(mat[l2][c1] - mat[l1][c1] != s3)
                        ok = false;
                    else
                    {///***
                    ///---
                    Sv[1] = s1;
                    Sv[2] = s2;
                    Sv[3] = s3;
                    Sv[4] = mat[l1][n] - mat[l1][c2];
                    Sv[5] = mat[l2][c2] - mat[l2][c1] - mat[l1][c2] + mat[l1][c1];
                    Sv[6] = mat[l2][n] - mat[l2][c2] - mat[l1][n] + mat[l1][c2];
                    Sv[7] = mat[n][c1] - mat[l2][c1];
                    Sv[8] = mat[n][c2] - mat[n][c1] - mat[l2][c2] + mat[l2][c1];
                    Sv[9] = mat[n][n] - mat[n][c2] - mat[l2][n] + mat[l2][c2];
                    sort(Sv + 1, Sv + 10);
                    for(i = 1; i <= 9; i++)
                        if(Sv[i] != S[i])
                        {ok = false;
                        break;}
                    if(ok == true)
                    {
                        if(l2 < r[2])
                        {r[1] = l1;
                        r[2] = l2;
                        r[3] = c1;
                        r[4] = c2;}
                        else
                        if(l2 == r[2])
                        {
                            if(l1 + l2 + c1 + c2 <= r[1] + r[2] + r[3] + r[4])
                            {r[1] = l1;
                            r[2] = l2;
                            r[3] = c1;
                            r[4] = c2;}
                        }
                    }
                    }///***
                    }///***
                    }///***
                }
            }
        }
    }
        cout << r[1] << " " << r[2] << " " <<  r[3] << " " <<  r[4];
    return 0;
}