Mai intai trebuie sa te autentifici.
Cod sursa(job #2232525)
| Utilizator | Data | 19 august 2018 20:48:11 | |
|---|---|---|---|
| Problema | Elimin | Scor | 70 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 1.41 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
short m, n, r, c, dus,
a[10000][10000], x[10000], o[10000];
int sum[10000], maxSum;
inline bool cmp(short a, short b) {
return sum[a] < sum[b];
}
void check() {
nth_element(o+1, o+r+1, o+m+1, cmp);
int s = 0;
for(int i = r+1; i <= m; i++)
s += sum[o[i]];
if(s > maxSum)
maxSum = s;
}
void bt(int k) { // combinari de n luate cate c;
if(k <= c) {
for(int i = x[k-1]+1; i <= n-c+k; i++) {
x[k] = i;
for(int j = 1; j <= m; j++)
sum[j] -= a[j][x[k]];
bt(k+1);
for(int j = 1; j <= m; j++)
sum[j] += a[j][x[k]];
x[k] = 0;
}
} else check();
}
int main()
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
scanf("%hi %hi %hi %hi", &m, &n, &r, &c);
if(m < n) {
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
scanf("%hi", &a[j][i]);
swap(m, n); swap(r, c);
} else {
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
scanf("%hi", &a[i][j]);
}
for(int i = 1; i <= m; i++) {
o[i] = i;
for(int j = 1; j <= n; j++)
sum[i] += a[i][j];
}
bt(1);
printf("%hi", maxSum);
return 0;
}
