Nu aveti permisiuni pentru a descarca fisierul grader_test48.ok
Cod sursa(job #111940)
Utilizator | Data | 2 decembrie 2007 16:01:04 | |
---|---|---|---|
Problema | Elimin | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.23 kb |
#include <stdio.h>
#include <stdlib.h>
int d[7300],b[1000],r,c,max,a[16][7300];
int compare( const void* a, const void* b ) {
int* arg1 = (int*) a;
int* arg2 = (int*) b;
if( *arg1 < *arg2 ) return -1;
else if( *arg1 == *arg2 ) return 0;
else return 1;
}
void back(int x,int n,int m,int c1)
{
int i,j,nr=0;
if (x==m+1)
{
for (i=0;i<=n;i++)
{
b[i]=0;
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (!d[j])
{
b[i-1]+=a[i][j];
}
qsort(b,n,sizeof(b[0]),compare);
nr=0;
for (i=r;i<n;i++)
nr+=b[i];
if (max<nr)
max=nr;
}
else
{
if (m-x+1>c-c1)
{
d[x]=0;
back(x+1,n,m,c1);
}
if (c1<c)
{
d[x]=1;
back(x+1,n,m,c1+1);
}
}
}
int main()
{
FILE *in,*out;
int i,j,n,m,aux;
in=fopen("elimin.in","r");
out=fopen("elimin.out","w");
fscanf(in,"%d%d%d%d",&n,&m,&r,&c);
max=-1;
if (m<=n)
{
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
fscanf(in,"%d",&a[i][j]);
back(1,n,m,0);
}
else
{
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
fscanf(in,"%d",&a[j][m-i+1]);
aux=r;
r=c;
c=aux;
back(1,m,n,0);
}
fprintf(out,"%d\n",max);
fclose(in);
fclose(out);
return 0;
}