Pagini recente » Cod sursa (job #76115) | Cod sursa (job #1676387) | Cod sursa (job #2156499) | Cod sursa (job #1583296) | Cod sursa (job #1022329)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define maxn 730
using namespace std;
int m,n,r,c;
int a[maxn][maxn], aa[maxn][maxn];
int smax=0;
int viz[maxn];
int sol[maxn];
int sum[maxn];
ifstream in("elimin.in");
ofstream out("elimin.out");
void restaurare()
{
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
aa[i][j]=a[i][j];
}
int compare(const void * a, const void * b)
{
return (*(int*)b- *(int*)a);
}
void verificare()
{
int k=0;
for (int i=0; i<r; i++)
for(int j=1; j<=n; j++)
aa[sol[i]][j]=0;
for (int j=1; j<=n; j++)
{
int s=0;
for (int i=1; i<=m; i++)
s+=aa[i][j];
sum[k]=s;
k++;
}
qsort(sum, k, sizeof(int), compare);
int s=0;
for (int i=0; i<k-c; i++)
{
s+=sum[i];
}
if (smax<s) smax=s;
restaurare();
}
void back(int k)
{
if (k==r)
{
verificare();
}
else if (k<n)
{
for(int i=1; i<=m; i++)
{
if ((!viz[i]) && (k==0))
{
sol[k]=i;
viz[i]=1;
back(k+1);
viz[i]--;
}
else if ((!viz[i]) && (sol[k-1]<i))
{
viz[i]=1;
sol[k]=i;
back(k+1);
viz[i]=0;
}
}
}
}
int main()
{
in>>m>>n>>r>>c;
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
{
in>>a[i][j];
}
if (m<n)
{
swap(m,n);
swap(r,c);
}
restaurare();
fill(viz, viz+m+1,0 );
back(0);
out<<smax;
return 0;
}