Pagini recente » Cod sursa (job #2732945) | Cod sursa (job #2049044) | Cod sursa (job #2837545) | Info Oltenia 2018 Proba pe Echipe Clasele 9 - 10 | Cod sursa (job #976446)
Cod sursa(job #976446)
#include <iostream>
#include <fstream>
#include <vector>
#define MAX_POSSIBLE 2147483647
using namespace std;
short mat[3][3]; ///vector< vector<short> > mat;
bool eliminln[3];
bool eliminclmn[3]; ///vector<bool> eliminln;
///vector<bool> eliminclmn;
vector<short> temp_ln;
short m,n,R,C,a;
int result,result_max=0;
long minclmn=MAX_POSSIBLE;
int sum_clmn(short z)
{
long s=0;
for(short i=0;i<m;i++)
s+=mat[i][z];
return s;
}
void elimin_ln(short sz)
{
for(short i=0;i<n;i++)
mat[sz][i]=0;
eliminln[sz]=true;
}
void elimin_clmn(short h)
{
for(short i=0;i<m;i++)
mat[i][h]=0;
eliminclmn[h]=true;
}
int min_clmn()
{
short p;
long d;
for(short i=0;i<n;i++)
{
d=sum_clmn(i);
if(d<=minclmn && eliminclmn[i]!=true)
{
p=i;
minclmn=d;
}
}
return p;
}
int sum()
{
long b=0;
for(short i=0;i<m;i++)
for(short j=0;j<n;j++)
b+=mat[i][j];
return b;
}
void backt_ln(short k)
{
if(k>R)
{
for(short l=0;l<C;l++)
{
a=min_clmn();
if(eliminclmn[a]!=true)
{
result=sum();
result=result-sum_clmn(a);
eliminclmn[a]=true;
}
}
if(result>result_max)
result_max=result;
}
else
for(short i=0;i<m;i++)
if(eliminln[i]!=true)
{
for(short j=0;j<n;j++)
temp_ln[j]=mat[i][j];
elimin_ln(i);
backt_ln(k+1);
for(short j=0;j<n;j++)
mat[i][j]=temp_ln[j];
eliminln[i]=false;
}
}
int main()
{
ifstream f("elimin.in");
ofstream g("elimin.out");
f>>m>>n>>R>>C;
for(short i=0;i<m;i++) ///mat.resize(m);
for(short j=0;j<n;j++) ///for(short i=0;i<m;i++)
f>>mat[i][j]; ///mat[i].resize(n);
///for(short i=0;i<m;i++)
///for(short j=0;j<n;j++)
///f>>mat[i][j];
///eliminln.resize(m);
///eliminclmn.resize(n);
temp_ln.resize(n);
backt_ln(1);
g<<result_max;
cout<<result_max;
}