Cod sursa(job #1939963)

Utilizator raluca1234Tudor Raluca raluca1234 Data 26 martie 2017 11:24:53
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

#define maxN 20
#define maxM 8000

using namespace std;

int N, M, R, C, ans;
int A[maxN+1][maxM+1], st[maxN+1], sum[maxM+1];

void solve(){
    memset(sum, 0, sizeof(sum));

    for (int j=1; j<=M; j++)
        for (int i=1; i<=N; i++)
            sum[j]+=A[i][j];

    for (int j=1; j<=M; j++)
        for (int i=1; i<=R; i++)
            sum[j]-=A[st[i]][j];

    sort(sum+1, sum+M+1);

    int crt=0;
    for (int i=C+1; i<=M; i++)
        crt+=sum[i];

    if (crt>ans)
        ans=crt;
}

void genComb(int k){
    int i;
    if (k==R+1)
        solve();
    else{
        for (i=st[k-1]+1; i<=N-R+k; i++){
            st[k]=i;
            genComb(k+1);
        }
    }
}

int main(){
    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);

    scanf("%d%d%d%d", &N, &M, &R, &C);

    if (N<=M){
        for (int i=1; i<=N; i++)
            for (int j=1; j<=M; j++)
                scanf("%d", &A[i][j]);
    }
    else{
        swap(N, M);
        swap(R, C);
        for (int i=1; i<=M; i++)
            for (int j=1; j<=N; j++)
                scanf("%d", &A[j][i]);
    }
    genComb(1);

    printf("%d\n", ans);

    return 0;
}