Cod sursa(job #1662852)
Utilizator | Data | 25 martie 2016 10:21:24 | |
---|---|---|---|
Problema | Zone | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.55 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;
}
}
viz[remove1(dp[i][j])]=0;
}
}
}
printf("%d %d %d %d",l1f,l2f,c1f,c2f);
return 0;
}