Cod sursa(job #2232525)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu 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;
}