Cod sursa(job #644092)
Utilizator | Data | 5 decembrie 2011 11:11:23 | |
---|---|---|---|
Problema | Elimin | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.44 kb |
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 5000
typedef struct pe
{int y,t;};
pe q[N];
int n,m,i,j,a[20][N],r,c,k,x,s[N],d,u,l[N],w[N];
int cmp(pe a,pe b)
{return a.t<b.t;}
int main()
{FILE *f=fopen("elimin.in","r"),*g=fopen("elimin.out","w");
fscanf(f,"%d%d%d%d",&n,&m,&r,&c);
if(n>m)
{for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fscanf(f,"%d",&a[j][i]);
x=n,n=m,m=x,x=r,r=c,c=x;}
else
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fscanf(f,"%d",&a[i][j]);
if(r)
for(k=1;k;)
{s[k]++;
if(s[k]<=n-r+k)
if(k==r)
{for(i=1;i<=r;i++)
l[s[i]]=1;
for(i=1;i<=m;i++)
q[i].t=0,q[i].y=i;
for(i=1;i<=n;i++)
if(!l[i])
for(j=1;j<=m;j++)
q[j].t+=a[i][j];
sort(q+1,q+m+1,cmp);
for(j=1;j<=c;j++)
w[q[j].y]=1;
for(i=1,d=0;i<=n;i++)
if(!l[i])
for(j=1;j<=m;j++)
if(!w[j])
d+=a[i][j];
for(i=1;i<=r;i++)
l[s[i]]=0;
for(j=1;j<=c;j++)
w[q[j].y]=0;
if(d>u)
u=d;}
else
k++,s[k]=s[k-1];
else
k--;}
else
{for(i=1;i<=m;i++)
q[i].t=0,q[i].y=i;
if(c)
{for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
q[j].t+=a[i][j];
sort(q+1,q+m+1,cmp);
for(j=1;j<=c;j++)
w[q[j].y]=1;}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(!w[j])
u+=a[i][j];}
fprintf(g,"%d",u);
return 0;}