Pagini recente » Monitorul de evaluare | Cod sursa (job #1980961) | Cod sursa (job #2494185) | Cod sursa (job #1349138) | Cod sursa (job #1527062)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define Nmax 15
#define Mmax 7300
class FileReader
{
private:
const static int Lmax = 5000;
int poz;
char s[Lmax + 1];
ifstream fin;
public:
FileReader(const char* file) {fin.open(file); poz = 0; fin.read(s, Lmax);}
inline void advance()
{
++poz;
if(poz == Lmax)
{
fin.read(s, Lmax);
poz = 0;
}
}
FileReader& operator >>(int& x)
{
while(!('0' <= s[poz] && s[poz] <= '9')) advance();
for(x = 0; '0' <= s[poz] && s[poz] <= '9'; advance())
x = x * 10 + s[poz] - '0';
return *this;
}
};
FileReader fin("elimin.in");
ofstream fout("elimin.out");
int m, n, r, c;
int nr[1 << Nmax];
int a[Nmax][Mmax], b[Mmax][Nmax], sum[Mmax];
void solve1() ;
void solve2() ;
int main()
{
for(int i = 1; i < (1 << Nmax); ++i) nr[i] = 1 + nr[i & (i - 1)];
fin >> m >> n >> r >> c;
if(m < n) solve1();
else solve2();
return 0;
}
void solve1() // m < n => back pe linii
{
int i, j, conf, s, smax;
for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) fin >> a[i][j];
for(smax = 0, conf = 0; conf < (1 << m); ++conf)
if(nr[conf] == r)
{
for(j = 0; j < n; ++j) sum[j] = 0;
for(i = 0; i < m; ++i)
if((conf & (1 << i)) == 0)
for(j = 0; j < n; ++j) sum[j] += a[i][j];
sort(sum, sum + n, greater<int>());
for(s = 0, j = 0; j < n - c; ++j) s += sum[j];
if(s > smax) smax = s;
}
fout << smax << '\n';
}
void solve2() // m >= n => back pe coloane
{
int i, j, conf, s, smax;
for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) fin >> b[i][j];
for(smax = 0, conf = 0; conf < (1 << n); ++conf)
if(nr[conf] == c)
{
for(j = 0; j < m; ++j) sum[j] = 0;
for(i = 0; i < m; ++i)
for(j = 0; j < n; ++j)
if((conf & (1 << j)) == 0)
sum[i] += b[i][j];
sort(sum, sum + m, greater<int>());
for(s = 0, j = 0; j < m - r; ++j) s += sum[j];
if(s > smax) smax = s;
}
fout << smax << '\n';
}