Mai intai trebuie sa te autentifici.
Cod sursa(job #910878)
Utilizator | Data | 11 martie 2013 10:04:11 | |
---|---|---|---|
Problema | Elimin | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.44 kb |
#include <fstream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
ifstream cin("elimin.in");
ofstream cout("elimin.out");
const int NMAX = 7294;
int M, N, R, C;
int *a[NMAX], sums[NMAX];
bool use[NMAX];
int e[32];
int ans;
void goLine(int k) {
if(k == R + 1) {
for(int j = 0;j < N;j++) {
sums[j + 1] = 0;
for(int i = 0;i < M;i++) {
if(!use[i]) {
sums[j + 1] += a[i][j];
}
}
}
nth_element(sums + 1,sums + C,sums + N + 1);
int sum = 0;
for(int j = C + 1;j <= N;j++) {
sum += sums[j];
}
ans = max(ans,sum);
} else {
for(int j = e[k - 1] + 1;j < M;j++) {
e[k] = j;
use[j] = true;
goLine(k + 1);
use[j] = false;
}
}
}
void goColumn(int k) {
if(k == C + 1) {
for(int i = 0;i < M;i++) {
sums[i + 1] = 0;
for(int j = 0;j < N;j++) {
if(!use[j]) {
sums[i + 1] += a[i][j];
}
}
}
nth_element(sums + 1,sums + R,sums + M + 1);
int sum = 0;
for(int j = R + 1;j <= M;j++) {
sum += sums[j];
}
ans = max(ans,sum);
} else {
for(int j = e[k - 1] + 1;j < N;j++) {
e[k] = j;
use[j] = true;
goColumn(k + 1);
use[j] = false;
}
}
}
int main()
{
cin>>M>>N>>R>>C;
for(int i = 0;i < M;i++) {
a[i] = new int[N];
for(int j = 0;j < N;j++) {
cin>>a[i][j];
}
}
e[0] = -1 ;
if(M <= N) {
goLine(1);
} else {
goColumn(1);
}
cout<<ans;
return 0;
}