Cod sursa(job #2232514)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 19 august 2018 20:23:25
Problema Elimin Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <algorithm>

using namespace std;

short m, n, r, c, dus,
      a[1001][1001], x[1001];

int sum[1001], o[1001], maxSum;

bool cmp(int a, int b) {
    return sum[a] < sum[b];
}

void check() {
    sort(o+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; 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];
    }
    x[0] = 0;
    bt(1);

    printf("%hi", maxSum);
    return 0;
}