Pagini recente » Cod sursa (job #1653953) | Cod sursa (job #321818) | Cod sursa (job #2134763) | Cod sursa (job #603758) | Cod sursa (job #2882885)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("elimin.in");
ofstream fout ("elimin.out");
const int MAXN=5000;
short n,m,r,c;
short a[MAXN][MAXN],b[MAXN][MAXN];
int v[MAXN],rez1;
void Solven (){
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
b[i][j]=a[i][j];
}
}
for (int i=1;i<=r;++i){
int x=v[i];
for (int j=1;j<=m;++j){
a[x][j]=0;
}
}
int s[MAXN],stotal=0;
for (int j=1;j<=m;++j){
s[j]=0;
for (int i=1;i<=n;++i){
s[j]+=a[i][j];
stotal+=a[i][j];
}
}
sort (s+1,s+m+1);
for (int i=1;i<=c;++i)
stotal-=s[i];
if (stotal>=rez1)
rez1=stotal;
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
a[i][j]=b[i][j];
}
}
}
void BackTrkN (int pos){
if (pos>r){
Solven ();
}
else{
for (int i=v[pos-1]+1;i<=n-r+pos;++i){
v[pos]=i;
BackTrkN (pos+1);
}
}
}
void Solvem (){
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
b[i][j]=a[i][j];
}
}
for (int i=1;i<=c;++i){
int x=v[i];
for (int j=1;j<=n;++j){
a[j][x]=0;
}
}
int s[MAXN],stotal=0;
for (int i=1;i<=n;++i){
s[i]=0;
for (int j=1;j<=m;++j){
s[i]+=a[i][j];
stotal+=a[i][j];
}
}
sort (s+1,s+n+1);
for (int i=1;i<=r;++i)
stotal-=s[i];
if (stotal>=rez1)
rez1=stotal;
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
a[i][j]=b[i][j];
}
}
}
void BackTrkM (int pos){
if (pos>c){
Solvem ();
}
else{
for (int i=v[pos-1]+1;i<=m-c+pos;++i){
v[pos]=i;
BackTrkM (pos+1);
}
}
}
int main()
{
fin >>n>>m>>r>>c;
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
fin >>a[i][j];
}
}
if (n<=m){
BackTrkN (1);
}
else{
BackTrkM (1);
}
fout <<rez1;
fin.close ();
fout.close ();
return 0;
}