Pagini recente » Cod sursa (job #1049868) | Cod sursa (job #1033014) | Cod sursa (job #1398745) | Cod sursa (job #2674958) | Cod sursa (job #3040693)
/*#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("elimin.in");
ofstream g("elimin.out");
int n, m, r, c;
int v[1005][1005];
vector <int> lin;
vector <int> sumcol;
long long s;
long long smax = 0;
void bk(int k)
{
if(k == n+1 && r == 0)
{
for(int i = 0; i<lin.size(); i++)
{
v[lin[i]][m+1] = -1;
}
for(int j = 1; j<=m; j++)
{
s = 0;
for(int i = 1; i<=n; i++)
{
if(v[i][m+1] == 0)
{
s += v[i][j];
}
}
sumcol.push_back(s);
}
sort(sumcol.begin(), sumcol.end());
s = 0;
for(int i = c; i<sumcol.size(); i++)
{
s += sumcol[i];
}
smax = max(smax, s);
for(int i = 0; i<lin.size(); i++)
{
v[lin[i]][m+1] = 0;
}
sumcol.clear();
return;
}
else if(k == n+1)
{
return;
}
else
{
if(r >= 1)
{
r--;
lin.push_back(k);
bk(k+1);
r++;
lin.pop_back();
bk(k+1);
}
else
{
bk(k+1);
}
}
}
int main()
{
f>>n>>m>>r>>c;
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<=m; j++)
{
f>>v[i][j];
}
}
bk(1);
g<<smax;
return 0;
}*/
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("elimin.in");
ofstream out ("elimin.out");
const int max_size1 = 1e2 + 1, max_size2 = 9e3 + 1;
int a[max_size1][max_size2], l[max_size1], cl[max_size2], m, n, r, c;
long long rez;
void check ()
{
for (int i = 1; i <= m; i++)
{
cl[i] = 0;
}
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= m; j++)
{
cl[j] += a[l[i]][j];
}
}
sort(cl + 1, cl + m + 1);
long long s = 0;
for (int i = m - c + 1; i <= m; i++)
{
s += cl[i];
}
rez = max(rez, s);
}
void bkt (int k)
{
for (int i = l[k - 1] + 1; i <= n - (r - k); i++)
{
l[k] = i;
if (k < r)
{
bkt(k + 1);
}
else
{
check();
}
}
}
int main ()
{
in >> n >> m >> r >> c;
r = n - r;
c = m - c;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (n <= m)
{
in >> a[i][j];
}
else
{
in >> a[j][i];
}
}
}
if (n > m)
{
swap(n, m);
swap(r, c);
}
bkt(1);
out << rez;
in.close();
out.close();
return 0;
}