Cod sursa(job #2477733)

Utilizator LucianTLucian Trepteanu LucianT Data 21 octombrie 2019 00:46:46
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int maxN=515;
const int K_Zones=9;

int n,m,k;
int mat[maxN][maxN];
long long pSum[maxN][maxN];

long long sums[K_Zones];
long long actSums[K_Zones];

long long getSum(int x1,int y1,int x2,int y2){
    return pSum[x2][y2]-pSum[x2][y1-1]-pSum[x1-1][y2]+pSum[x1-1][y1-1];
}

bool searchSum(long long sm){
    for(int i=0;i<K_Zones;i++){
        if(sums[i]==sm){
            return true;
        }
    }
    return false;
}

int main(){
    ifstream f("zone.in");
    ofstream g("zone.out");

    f>>n;
    for(int i=0;i<K_Zones;i++){
        f>>sums[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f>>mat[i][j];
            pSum[i][j]=mat[i][j]+pSum[i-1][j]+pSum[i][j-1]-pSum[i-1][j-1];
        }
    }

    sort(sums,sums+K_Zones);

    for(int l1=1;l1<n;l1++){
        for(int c1=1;c1<n;c1++){
            if(searchSum(getSum(1,1,l1,c1))){
                for(int l2=l1+1;l2<n;l2++){
                    if(searchSum(getSum(l1+1,1,l2,c1))){
                        for(int c2=c1+1;c2<n;c2++){
                            //HARDCODEALA
                            int sz=0;
                            actSums[sz++]=getSum(1,1,l1,c1);
                            actSums[sz++]=getSum(1,c1+1,l1,c2);
                            actSums[sz++]=getSum(1,c2+1,l1,n);
                            
                            actSums[sz++]=getSum(l1+1,1,l2,c1);
                            actSums[sz++]=getSum(l1+1,c1+1,l2,c2);
                            actSums[sz++]=getSum(l1+1,c2+1,l2,n);
                            
                            actSums[sz++]=getSum(l2+1,1,n,c1);
                            actSums[sz++]=getSum(l2+1,c1+1,n,c2);
                            actSums[sz++]=getSum(l2+1,c2+1,n,n);

                            sort(actSums,actSums+K_Zones);

                            bool equal=true;
                            for(int i=0;i<K_Zones;i++){
                                if(actSums[i]!=sums[i]){
                                    equal=false;
                                    break;
                                }
                            }
                            if(equal){
                                g<<l1<<" "<<l2<<" "<<c1<<" "<<c2;
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}