Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1452178) | Cod sursa (job #3336967) | Cod sursa (job #3315078)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("elimin.in");
ofstream fout("elimin.out");
int n,m,a[555][555],rez,r,c;
vector<int>x;
void procesare1(){
vector<bool>t(n+1,false);
for(int i=1;i<=r;i++) t[x[i]]=1;
int sum=0;
vector<int>sc;
for(int j=1;j<=m;j++){
int csum=0;
for(int i=1;i<=n;i++){
if(!t[i]) csum+=a[i][j];
}
sc.push_back(csum);
}
sort(sc.begin(),sc.end());
for(int i=c;i<sc.size();i++) sum+=sc[i];
rez=max(rez,sum);
}
void back1(int step){
if(step>r){
procesare1();
return;
}
for(int i=x[step-1]+1;i<=n-r+step;i++){
x[step]=i;
back1(step+1);
}
}
void procesare2(){
vector<bool>t(m+1,false);
for(int i=1;i<=c;i++)t[x[i]]=1;
int sum=0;
vector<int> sc;
for(int i=1;i<=n;i++){
int csum=0;
for(int j=1;j<=m;j++){
if(!t[j]) csum+=a[i][j];
}
sc.push_back(csum);
}
sort(sc.begin(),sc.end());
for(int i=r;i<sc.size();i++) sum+=sc[i];
rez=max(rez,sum);
}
void back2(int step){
if(step>c){
procesare2();
return;
}
for(int i=x[step-1]+1;i<=m-c+step;i++){
x[step]=i;
back2(step+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){
x.resize(n+1);
back1(1);
fout<<rez;
}else{
x.resize(m+1);
back2(1);
fout<<rez;
}
return 0;
}