Mai intai trebuie sa te autentifici.
Cod sursa(job #150033)
Utilizator | Data | 6 martie 2008 15:20:40 | |
---|---|---|---|
Problema | Elimin | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.34 kb |
#include<stdio.h>
#include<algorithm>
#define NMAX 551
using namespace std;
int cmpf(long a, long b)
{
return (a<b);
}
long b,z[NMAX],x[NMAX][NMAX],i,j,k,l,a,s,rez,n,m,ln,cl;
char y[17];
void sol()
{
z[0]=0;
s=0;
for (i=1;i<=n;++i)
{
z[0]++;
z[i]=0;
for (j=1;j<=m;++i)
if (y[j]==0)
z[i]+=x[i][j];
s+=z[i];
}
sort(z+1,z+n+1,cmpf);
for (i=1;i<=ln;i++)
s-=z[i];
if (s>rez)
rez=s;
}
void back(int p, int k)
{
if (p<=m&&k<cl)
{
back(p+1,k);
y[p]=1;
back(p+1,k+1);
y[p]=0;
}
else
if (k==cl)
{
z[0]=0;
s=0;
for (i=1;i<=n;++i)
{
z[0]++;
z[i]=0;
for (j=1;j<=m;++i)
if (y[j]==0)
z[i]+=x[i][j];
s+=z[i];
}
sort(z+1,z+n+1,cmpf);
for (i=1;i<=ln;i++)
s-=z[i];
if (s>rez)
rez=s;
}
// sol();
}
int main()
{
freopen("elimin.in","r",stdin);
freopen("elimin.out","w",stdout);
scanf("%ld%ld%ld%ld",&n,&m,&ln,&cl);
rez=-100000;
if (m<=15)
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
scanf("%ld",&x[i][j]);
else
{
a=n; n=m; m=a;
a=ln; ln=cl; cl=a;
for (j=1;j<=m;j++)
for (i=1;i<=n;i++)
scanf("%ld",&x[i][j]);
}
back(1,0);
printf("%ld\n",rez);
return 0;
}
/* a=1;
while (a)
{
a=0;
for (i=1;i<n;i++)
if (z[i]>z[i+1])
{
a=z[i];
z[i]=z[i+1];
z[i+1]=a;
a=1;
}
}
*/