Cod sursa(job #2306349)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 22 decembrie 2018 09:23:34
Problema Elimin Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("elimin.in");
ofstream g("elimin.out");
int Stack[91], sum, suma[7295], suma2[7295], A[7295], maxSum, N, M, R, C;

void check () {
    sum = 0;
    for (int cnt = 0; cnt < M; ++cnt) {
        suma2[cnt] = suma[cnt];
        sum += suma[cnt];
    }

    for (int cnt = 0; cnt < R; ++cnt) {
        int poz = Stack[cnt] * M;
        for (int j = 0; j < M; ++j) {
            suma2[j] -= A[poz];
            sum -= A[poz];
            ++poz;
        }
    }
    sort (suma2, suma2 + M);
    for (int cnt = 0; cnt < C; ++cnt)
        sum -= suma2[cnt];
    if (sum > maxSum)
        maxSum = sum;
}

void backt (int level) {
    if (level == R) {
        check();
        return;
    }
    for (int i = Stack[level - 1] + 1; i <= N - (R - level); ++i) {
        Stack[level] = i;
        backt(level + 1);
    }
}
int main()
{
    f >> N >> M >> R >> C;
    if (N > M) {
        swap(N, M);
        swap(R, C);
    }
    int k = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j) {
            f >> A[k];
            suma[j] += A[k];
            ++k;
        }
    for (int x = 0; x <= N - R; ++x) {
        Stack[0] = x;
        backt(1);
    }
    g << maxSum;
    return 0;
}