Cod sursa(job #1065121)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 22 decembrie 2013 20:00:22
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.51 kb
#include<fstream>
#include<algorithm>
#include<cstdio>
#define LG 2500000
using namespace std;
int n,m,R,C,mat[610][610],sol,sumC[7300],ind;
int lin[20],v[7300];
char buffer[LG];
  
inline void Citeste(int &x)
{
    while(buffer[ind]<'0' || '9'<buffer[ind])
    {
        ind++;
        if(ind==LG)
        {
            fread(buffer,1,LG,stdin);
            ind=0;
        }
    }
    x=0;
    while('0'<=buffer[ind] && buffer[ind]<='9')
    {
        x=x*10+buffer[ind]-'0';
        ind++;
        if(ind==LG)
        {
            fread(buffer,1,LG,stdin);
            ind=0;
        }
    }
}

inline void Verif()
{
	int i,j,now=0;
	for(j=1;j<=m;j++)
	{
		v[j]=sumC[j];
		for(i=1;i<=R;i++)
			v[j]-=mat[lin[i]][j];
	}
	nth_element(v+1,v+C,v+m+1);
	for(i=C+1;i<=m;i++)
		now+=v[i];
	sol=max(sol,now);
}

inline void Back(int pas)
{
	if(pas==R+1)
		Verif();
	else
	{
		int i;
		for(i=lin[pas-1]+1;i<=n-R+pas;i++)
		{
			lin[pas]=i;
			Back(pas+1);
		}
	}
}

int main()
{
	int i,j;
	freopen("elimin.in","r",stdin);
	fread(buffer,1,LG,stdin);
	Citeste(n); Citeste(m); Citeste(R); Citeste(C);
	if(n<=m)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				Citeste(mat[i][j]);
				sumC[j]+=mat[i][j];
			}
		}
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				Citeste(mat[j][i]);
				sumC[i]+=mat[j][i];
			}
		}
		swap(n,m);
		swap(R,C);
	}
	
	Back(1);
	
	freopen("elimin.out","w",stdout);
	printf("%d\n",sol);
	return 0;
}