Cod sursa(job #2486723)

Utilizator Constantin.Dragancea Constantin Constantin. Data 3 noiembrie 2019 13:42:58
Problema Zone Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <bits/stdc++.h>
using namespace std;

#define N 520
int n, a[N][N], s[20];
unordered_map <int,int> M;

int main(){
    freopen("zone.in", "r", stdin);
    freopen("zone.out", "w", stdout);
    cin >> n;
    for (int i=0; i<9; i++) cin >> s[i], M[s[i]]++;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) cin >> a[i][j];
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
    for (int i=1; i<n-1; i++){
        for (int j=1; j<n-1; j++){
            if (!M[a[i][j]]) continue;
            //cout << i << ' ' << j << "lol\n";
            M[a[i][j]]--;
            bool flag = 1;
            for (int i2=i+1; i2<n; i2++){
                for (int j2=j+1; j2<n; j2++){
                    if (!M[a[i][j2] - a[i][j]]) flag = 0;
                    else M[a[i][j2] - a[i][j]]--;
                    if (!M[a[i][n] - a[i][j2]]) flag = 0;
                    else M[a[i][n] - a[i][j2]]--;
                    if (!M[a[i2][j] - a[i][j]]) flag = 0;
                    else M[a[i2][j] - a[i][j]]--;
                    if (!M[a[i2][j2] - a[i][j2] - a[i2][j] + a[i][j]]) flag = 0;
                    else M[a[i2][j2] - a[i][j2] - a[i2][j] + a[i][j]]--;
                    if (!M[a[i2][n] - a[i2][j2] - a[i][n] + a[i][j2]]) flag = 0;
                    else M[a[i2][n] - a[i2][j2] - a[i][n] + a[i][j2]]--;
                    if (!M[a[n][j] - a[i2][j]]) flag = 0;
                    else M[a[n][j] - a[i2][j]]--;
                    if (!M[a[n][j2] - a[n][j] - a[i2][j2] + a[i2][j]]) flag = 0;
                    else M[a[n][j2] - a[n][j] - a[i2][j2] + a[i2][j]]--;
                    if (!M[a[n][n] - a[n][j2] - a[i2][n] + a[i2][j2]]) flag = 0;
                    else M[a[n][n] - a[n][j2] - a[i2][n] + a[i2][j2]]--;
                    if (flag){
                        cout << i << ' ' << i2 << ' ' << j << ' ' << j2 << '\n';
                        return 0;
                    }
                    else{
                        //cout << i2 << ' ' << j2 << '\n';
                        M.clear();
                        for (int fo=0; fo<9; fo++) M[s[fo]]++;
                        M[a[i][j]]--;
                        flag = 1;
                    }
                }

            }

        }
    }
    return 0;
}