Pagini recente » Cod sursa (job #1009072) | Cod sursa (job #1944728) | Cod sursa (job #2735872) | Cod sursa (job #2284576) | Cod sursa (job #1071544)
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#define N_MAX 2000
using namespace std;
short a[N_MAX][N_MAX];
short d[20], b[20];
short m,n,r,c;
int scade[1000];
int sumalinie[1000];
int suma=0;
int sumamax=0;
void back(int k)
{
if(k-1 == c) //afisam solutia
{
//for(int ii=0;ii<c;ii++){
for(int j=0;j<n;j++){
for(int i = 1; i <= c;i++){
//if(j+1==i)
//cout<<d[i]<<" ";
//cout<<d[i]<<" ";
scade[j]+=a[j][d[i]-1];
//sumalinie[ii]+=a[ii][j];
}
//scade+=a[ii][d[i]-1];
// }
//scade+=a[l][d[i]-1];
//cout<<sumalinie[0]<<" "<<scade[0]<<endl;
//cout<<scade[j]<<" ";
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
sumalinie[i]+=a[i][j];
}
sumalinie[i]-=scade[i];
//cout<<sumalinie[i]<<endl;
}
//sort(sumalinie+0, sumalinie+n);
nth_element(sumalinie+0,sumalinie+r,sumalinie+n);
for(int i=r;i<n;i++){
suma+=sumalinie[i];
}
if(sumamax<suma)
sumamax=suma;
// cout<<suma<<endl;
suma=0;
//cout<<scade[l];
//l++;
//cout<<d[i];
memset(scade,0,N_MAX);
memset(sumalinie,0,N_MAX);
// cout<<endl;
}
else
{
for(int i = 1; i <= m; i++)
if(!b[i] && d[k-1] < i) //ne asiguram ca generam solutiile crescatoare si unice
{
d[k] = i;
b[i] = 1; //o folosim
back(k+1); //trecem la pasul urmator
b[i] = 0; //o eliberam
}
}
}
int main()
{
int i,j;
ifstream f("elimin.in");
ofstream g("elimin.out");
f>>n>>m>>r>>c;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
f>>a[i][j];
}
}
if(n<m){
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(j>i)
swap(a[i][j],a[j][i]);
}
}
swap(n,m);
swap(r,c);
}
back(1);
g<<sumamax;
return 0;
}