Cod sursa(job #2541480)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 8 februarie 2020 14:16:43
Problema Zone Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.56 kb
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>

using namespace std;

const int INF = 2e9;
const int N = 512;
const int S = 9;

long long a[5 + N][5 + N];
long long s[5 + N][5 + N];
long long sum[5 + S], sum_aux[5 + S];
long long ans[4] = {INF, INF, INF, INF};

int main() {
    freopen("zone.in", "r", stdin);
    freopen("zone.out", "w", stdout);
    long long n, s1, s2, s3, l1, l2, c1, c2;

    scanf("%lld", &n);
    for(int i = 1; i <= S; i++) scanf("%lld", &sum[i]);
    sort(sum + 1, sum + S + 1);

    for(long long i = 1; i <= n; i++) {
        for(long long j = 1; j <= n; j++) {
            scanf("%lld", &a[i][j]);
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }

    for(l1 = 1; l1 < n; l1++) {
        for(long long i = 1; i < S - 1; i++) {
            long long s1 = sum[i];

            for(long long j = i + 1; j < S; j++) {
                long long s2 = sum[j];

                for(long long k = j + 1; k <= S; k++) {
                    long long s3 = sum[k];

                    // caut binar prima coloana
                    c1 = 1;
                    long long pas = N;
                    while(pas) {
                        if(c1 + pas < n - 1 && s[l1][c1 + pas] <= s1)
                            c1 += pas;
                        pas >>= 1;
                    }

                    if(s[l1][c1] == s1) {

                        // caut binar a doua coloana
                        c2 = c1 + 1;
                        pas = N;
                        while(pas) {
                            if(c2 + pas < n && s[l1][c2 + pas] - s[l1][c1] <= s2)
                                c2 += pas;
                            pas >>= 1;
                        }

                        if(s[l1][c2] - s[l1][c1] == s2) {

                            // caut binar a doua linie
                            l2 = l1 + 1;
                            pas = N;
                            while(pas) {
                                if(l2 + pas < n && s[l2 + pas][c1] - s[l1][c1] <= s3)
                                    l2 += pas;
                                pas >>= 1;
                            }

                            if(s[l2][c1] - s[l1][c1] == s3) {

                                // am gasit toate sumele
                                sum_aux[1] = s1;
                                sum_aux[2] = s2;
                                sum_aux[3] = s3;
                                sum_aux[4] = s[l1][n] - s[l1][c2];
                                sum_aux[5] = s[l2][c2] - s[l1][c2] - s[l2][c1] + s[l1][c1];
                                sum_aux[6] = s[l2][n] - s[l2][c2] - s[l1][n] + s[l1][c2];
                                sum_aux[7] = s[n][c1] - s[l2][c1];
                                sum_aux[8] = s[n][c2] - s[l2][c2] - s[n][c1] + s[l2][c1];
                                sum_aux[9] = s[n][n] - s[l2][n] - s[n][c2] + s[l2][c2];

                                sort(sum_aux + 1, sum_aux + S + 1);

                                bool ok(true);
                                for(int x = 1; x <= S; x++) {
                                    if(sum_aux[x] != sum[x])
                                        ok = false;
                                }

                                if(ok == true) {
                                    if(c1 < ans[1]) {
                                        ans[0] = l1;
                                        ans[1] = c1;
                                        ans[2] = l2;
                                        ans[3] = c2;
                                    } else if(c1 == ans[1]) {
                                        if(l2 < ans[2]) {
                                            ans[0] = l1;
                                            ans[1] = c1;
                                            ans[2] = l2;
                                            ans[3] = c2;
                                        } else if(l2 == ans[1]) {
                                            if(c2 <= ans[3]) {
                                                ans[0] = l1;
                                                ans[1] = c1;
                                                ans[2] = l2;
                                                ans[3] = c2;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    printf("%lld %lld %lld %lld\n", ans[0], ans[2], ans[1], ans[3]);
    return 0;
}