Cod sursa(job #2232488)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 19 august 2018 17:22:34
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <algorithm>

using namespace std;

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

int sum[522], maxSum, s;

void check() {
    for(int i = 1; i <= m; i++)
        sum[i] = 0;

    for(int i = 1; i <= n-c; i++)
        for(int j = 1; j <= m; j++)
            sum[j] += a[j][x[i]];
    sort(sum+1, sum+m+1);

    s = 0;
    for(int i = r+1; i <= m; i++)
        s += sum[i];
    if(s > maxSum)
        maxSum = s;
}

void bt(int k) { // combinari de n luate cate n-c;
    if(k <= n-c)
        for(int i = x[k-1]+1; i <= c+k; i++) {
            x[k] = i;
            bt(k+1);
            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]);
    }
    x[0] = 0;
    bt(1);

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