Cod sursa(job #3304390)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 23 iulie 2025 10:51:48
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("elimin.in");
ofstream out("elimin.out");

const int nmax = 7294;
int n, m, a[nmax + 2];
int base[nmax + 2];

int dx, dy;

int getidx(int i, int j){
    return (i - 1) * m + j;
}

int waysmsk, sum, bestt;
int sumcol[nmax + 2];

void solve(){
    for(int j = 1; j <= m; j++)
        sumcol[j] = 0;

    for(int i = 1; i <= n; i++){
        if(waysmsk & (1 << (i - 1))){ continue; }
        for(int j = 1; j <= m; j++)
            sumcol[j] += a[getidx(i, j)];
    }

    sort(sumcol + 1, sumcol + 1 + m); sum = 0;
    for(int j = dy + 1; j <= m; j++)
        sum += sumcol[j];
    bestt = max(bestt, sum);

    return;
}

void bkt(int lastt, int countt){
    if(countt == dx){
        solve();
        return;
    }

    for(int i = lastt + 1; i <= n; i++){
        waysmsk |= (1 << (i - 1));
        bkt(i, countt + 1);
        waysmsk ^= (1 << (i - 1));
    }
}

int main(){

    in>>n>>m>>dx>>dy;
    for(int i = 1; i <= n * m; i++)
        in>>a[i], base[i] = a[i];

    if(n > m){
        int idx = 0;
        for(int j = 1; j <= m; j++)
            for(int i = n; i >= 1; i--){
                a[++idx] = base[getidx(i, j)];
        }
        swap(n, m); swap(dx, dy);
    }

    bkt(0, 0);
    out<<bestt<<"\n";

    return 0;
}