Cod sursa(job #2482066)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 27 octombrie 2019 19:22:13
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 kb
#include<fstream>
#include<vector>
#include<map>
using namespace std;
ifstream cin("zone.in");
ofstream cout("zone.out");

int n;
map<long long ,int> M;
long long sp[515][515];
vector<int> sol(4,1000),cdt;
vector<pair<int,int> > sq1,sq2;
vector<long long> allsq;

long long d(int x1,int y1,int x2,int y2){

    if(x1<=x2 && y1<=y2)
        return sp[x2][y2]-sp[x2][y1-1]-sp[x1-1][y2]+sp[x1-1][y1-1];
    else return 0;

}

int ok(map<long long,int> M){

    for(int i=0;i<allsq.size();i++){

        if(M.count(allsq[i])==0 || M[allsq[i]]==0)
            return 0;

        --M[allsq[i]];

    }

    return 1;

}

int main(){

    cin>>n;
    for(int i=1;i<=9;i++){

        long long x;
        cin>>x;
        M[x]++;

    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){

            cin>>sp[i][j];
            sp[i][j]+=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1];

        }

    for(int i=1;i<n-1;i++)
        for(int j=1;j<n-1;j++)
            if(M.count(d(1,1,i,j)))
                sq1.push_back(make_pair(i,j));

    for(int i=n;i>=2;i--)
        for(int j=n;j>=2;j--)
            if(M.count(d(i+1,j+1,n,n)))
                sq2.push_back(make_pair(i,j));

    for(int i=0;i<sq1.size();i++)
        for(int j=0;j<sq2.size();j++){

            int x1=sq1[i].first;
            int y1=sq1[i].second;
            int x2=sq2[j].first;
            int y2=sq2[j].second;

            cdt.clear();
            allsq.clear();

            cdt.push_back(x1);
            cdt.push_back(y1);
            cdt.push_back(x2);
            cdt.push_back(y2);

            allsq.push_back(d(1,1,x1,y1));    //1
            allsq.push_back(d(1,y1+1,x1,y2));    //2
            allsq.push_back(d(1,y2+1,x1,n));    //3
            allsq.push_back(d(x1+1,1,x2,y1)); //4
            allsq.push_back(d(x1+1,y1+1,x2,y2)); //5
            allsq.push_back(d(x1+1,y2+1,x2,n)); //6
            allsq.push_back(d(x2+1,1,n,y1)); //7
            allsq.push_back(d(x2+1,y1+1,n,y2)); //8
            allsq.push_back(d(x2+1,y2+1,n,n)); //9

            if(!ok(M))
                continue;

            sol=min(sol,cdt);

        }

    cout<<sol[0]<<' '<<sol[2]<<' '<<sol[1]<<' '<<sol[3];

}