Pagini recente » Cod sursa (job #2858870) | Cod sursa (job #2026870) | Cod sursa (job #1958825) | Cod sursa (job #2692458) | Cod sursa (job #3138396)
#include <bits/stdc++.h>
using namespace std;
int n, m, r, c, ans;
vector < vector <int> > a;
vector <int> columns, rows, sol;
void calculateRow()
{
for(int j = 1; j <= m; j ++)
columns[j] = 0;
// for(int i = 1; i <= n; i ++)
// cout << sol[i - 1] << " ";
// cout << "\n";
for(int i = 1; i <= n; i ++)
{
if(sol[i - 1])
for(int j = 1; j <= m; j ++)
columns[j] += a[i][j];
}
sort(columns.begin() + 1, columns.end());
int sum = 0;
for(int j = c + 1; j <= m; j ++)
sum += columns[j];
ans = max(ans, sum);
}
void calculateColumn()
{
for(int i = 1; i <= n; i ++)
rows[i] = 0;
for(int j = 1; j <= m; j ++)
{
if(sol[j - 1])
for(int i = 1; i <= n; i ++)
rows[i] += a[i][j];
}
sort(rows.begin() + 1, rows.end());
int sum = 0;
for(int i = r + 1; i <= n; i ++)
sum += rows[i];
ans = max(ans, sum);
}
void solveRow(int k, int cnt)
{
if(k == n)
{
if(cnt == r)
calculateRow();
return;
}
if(cnt < r)
{
sol[k] = 0;
solveRow(k + 1, cnt + 1);
}
sol[k] = 1;
solveRow(k + 1, cnt);
}
void solveColumn(int k, int cnt)
{
if(k == m)
{
if(cnt == c)
calculateColumn();
return;
}
if(cnt < c)
{
sol[k] = 0;
solveColumn(k + 1, cnt + 1);
}
sol[k] = 1;
solveColumn(k + 1, cnt);
}
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
cin >> n >> m >> r >> c;
a.assign(n + 1, vector <int> (m + 1));
for(int i = 1 ; i <= n; i ++)
for(int j = 1; j <= m; j ++)
cin >> a[i][j];
if(n <= m)
sol.resize(n + 1), columns.resize(m + 1), solveRow(0, 0);
else
sol.resize(m + 1), rows.resize(n + 1), solveColumn(0, 0);
cout << ans;
return 0;
}