Cod sursa(job #1812185)

Utilizator giotoPopescu Ioan gioto Data 21 noiembrie 2016 21:31:23
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int Sol, sum, n, m, l, c, Last[10001], C[10001], C2[10001], a[21][7295];
inline void back(int k, int Last){
    if(k == l + 1){
        for(int i = 1; i <= m ; ++i)
            C2[i] = C[i];
        nth_element(C2 + 1, C2 + c + 1, C2 + m + 1);
        int aux = sum;
        for(int i = 1; i <= c ; ++i)
            sum -= C2[i];
        if(sum > Sol) Sol = sum;
        sum = aux;
        return ;
    }
    for(int i = Last + 1; i <= n ; ++i){
        for(int j = 1; j <= m ; ++j)
            C[j] -= a[i][j], sum -= a[i][j];
        back(k + 1, i);
        for(int j = 1; j <= m ; ++j)
            C[j] += a[i][j], sum += a[i][j];
    }
}
int main()
{
    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &l, &c);
    for(int i = 1; i <= n ; ++i)
        for(int j = 1; j <= m ; ++j){
            if(n >= m)
                scanf("%d", &a[i][j]), sum += a[i][j];
            else
                scanf("%d", &a[j][i]), sum += a[j][i];
        }
    if(n > m){
        int aux = m; m = n; n = aux;
            aux = l; l = c; c = aux;
    }
    for(int i = 1; i <= n ; ++i)
        for(int j = 1; j <= m ; ++j)
            C[j] += a[i][j];
    back(1, 0);
    printf("%d", Sol);
    return 0;
}