Cod sursa(job #1071869)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 ianuarie 2014 16:59:35
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.85 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;
}