Cod sursa(job #1662849)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 25 martie 2016 10:18:47
Problema Zone Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.51 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define N 520

using namespace std;

int m[N][N];
long long dp[N][N];
long long sum[10],viz[10];
int k;


int caut_sum(int t)
{

    for(k=0; k<9; k++)
    {
        if(viz[k]==0 && t==sum[k] )
        {
            viz[k]=1;
            return k;
        }
    }
    return -1;
}

int remove1(int t){
    for(k=0; k<9; k++){
        if( t==sum[k] ){
            return k;
        }
    }
    return -1;
}


int l1f=1<<30,c1f=1<<30,l2f=1<<30,c2f=1<<30;


int main()
{
    int i,n,j;
    int i1,j1;

    int l1,c1,l2,c2;

    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);

    scanf("%d",&n);

    for(i=0; i<9; i++)
    {
        scanf("%lld",&sum[i]);
    }

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            scanf("%d",&m[i][j]);
        }
    }

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+m[i][j];
        }
    }


    for(i=1; i<n; i++)
    {
        for(j=1; j<n; j++)
        {
            if( caut_sum(dp[i][j]) >= 1 )
            {
                l1=i;
                c1=j;
                for(j1=j+1; j1<n; j1++)
                {
                    if( caut_sum( dp[i][j1]-dp[l1][c1] )>=0){
                        if( caut_sum( dp[l1][n]-dp[l1][j1] )>=0   ){
                            c2=j1;
                            for(i1=i+1; i1<n; i1++){
                                if( caut_sum( dp[i1][c1]-dp[l1][c1] )>=0  ){

                                    if(caut_sum( dp[i1][c2]-dp[i1][c1]-dp[l1][c2]+dp[l1][c1] )>=0 ){

                                        if( caut_sum( dp[i1][n]-dp[i1][c2]-dp[l1][n]+dp[l1][c2] )>=0 ){

                                            if( caut_sum( dp[n][c1]-dp[i1][c1]  ) >=0 ){

                                                if( caut_sum( dp[n][c2]-dp[n][c1]-dp[i1][c2]+dp[i1][c1]  )>=0 ){

                                                    if(caut_sum( dp[n][n] - dp[n][c2] - dp[i1][n] +dp[i1][c2] )>=0  ){

                                                        if(l1<l1f){
                                                            l1f=l1; l2f=i1;  c1f=c1;  c2f=c2;
                                                        }else if(l1==l1f){
                                                            if(c1<c1f){
                                                                l1f=l1; l2f=i1;  c1f=c1;  c2f=c2;
                                                            }else if(c1==c1f){
                                                                if(i1<l2f){
                                                                    l1f=l1; l2f=i1;  c1f=c1;  c2f=c2;
                                                                }else if(i1==l2f){
                                                                    if(c2<c2f){
                                                                        l1f=l1; l2f=i1;  c1f=c1;  c2f=c2;
                                                                    }
                                                                }


                                                            }

                                                        }
                                                        viz[remove1( dp[n][n] - dp[n][c2] - dp[i1][n] +dp[i1][c2] )]=0;
                                                    }
                                                    viz[remove1( dp[n][c2]-dp[n][c1]-dp[i1][c2]+dp[i1][c1]  )]=0;
                                                }
                                                viz[remove1(dp[n][n] - dp[n][c2] - dp[i1][n] +dp[i1][c2])]=0;
                                            }
                                            viz[remove1( dp[i1][n]-dp[i1][c2]-dp[l1][n]+dp[l1][c2] )]=0;
                                        }
                                        viz[remove1( dp[i1][c2]-dp[i1][c1]-dp[l1][c2]+dp[l1][c1] )]=0;
                                    }
                                    viz[remove1( dp[i1][c1]-dp[l1][c1] ) ]=0;
                                }
                            }
                            viz[remove1( dp[l1][n]-dp[l1][j1] )]=0;
                        }
                        viz[remove1( dp[i][j1]-dp[l1][c1] )]=0;

                    }

                }
            }
        }
    }

    printf("%d %d %d %d",l1f,l2f,c1f,c2f);


    return 0;
}