Cod sursa(job #460926)
#include <stdio.h>
int m,n, r, c;
int matrice[8000][8000];
int coloane[8000];
int coloanes[8000];
int randuri[8000];
int idxcoloane[8000];
int idxranduri[8000];
long max;
long suma;
void verifica()
{
int i;
long q = suma;
for(i=0;i<r;++i)
q -= randuri[idxranduri[i]];
for(i=0;i<c;++i)
q -= coloane[idxcoloane[i]];
for(i=0;i<r;++i)
{
for(int j=0;j<c;++j)
q += matrice[idxranduri[i]][idxcoloane[j]];
}
if(q > max)
max = q;
}
int main(void)
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
scanf("%d %d %d %d", &m, &n, &r, &c);
int i;
suma = 0;
for(i=0;i<m;++i)
{
int c = 0;
for(int j=0;j<n;++j)
{
scanf("%d ", &matrice[i][j]);
suma += matrice[i][j];
}
}
for(int j=0;j<n;++j)
{
int c = 0;
for(int i=0;i<m;++i)
{
c += matrice[i][j];
}
coloane[j] = c;
}
int rand = 0;
idxranduri[0] = 0;
while(idxranduri[0] < m)
{
if(idxranduri[rand] < m)
{
++rand;
idxranduri[rand] = idxranduri[rand-1];
}
else
--rand;
if(rand >= r)
{
for(i=0; i<m; ++i)
coloanes[i] = coloane[i];
for(i=0;i<r;++i)
{
for(int j=0;j<m;++j)
coloanes[j] -= matrice[idxranduri[i]][j];
}
for(i=m-1;i>0;--i)
{
for(int j=0;j<i;++j)
{
if(coloanes[j] > coloanes[j+1])
{
int t = coloanes[j];
coloanes[j] = coloanes[j+1];
coloanes[j+1] = t;
}
}
}
int sum = 0;
for(i=c;i<m;++i)
sum += coloanes[i];
if(sum > max)
max = sum;
}
++idxranduri[rand];
}
printf("%ld\n", max);
return 0;
}