Cod sursa(job #2676973)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 25 noiembrie 2020 16:08:39
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <algorithm>
using namespace std;
const int DIV_MAX = 15;
const int NMAX = 7294;
int a[DIV_MAX][NMAX];
int col[NMAX];
int ord[NMAX];
int n, m, r, c;
int st[DIV_MAX + 1];
int maxy = 0;
int sum_all ( int m ) {
    int s = 0;
    for ( int i = 0; i < m; i++ )
        s += col[i];
    return s;
}
bool cmp ( int a, int b ) {
    return col[a] < col[b];
}
void bkt ( int k ) {
    if ( k == r + 1 ) {
        nth_element ( ord, ord + c, ord + m, cmp );
        int s = sum_all ( m ), smin = 0;
        for ( int i = 0; i < c; i++ )
            smin += col[ord[i]];
        maxy = s - smin > maxy ? s - smin : maxy;
        return;
    }
    for ( int i = st[k - 1] + 1; i < n - (r - k); i++ ) {
        st[k] = i;
        for ( int j = 0; j < m; j++ )
            col[j] -= a[i][j];
        bkt ( k + 1 );
        for ( int j = 0; j < m; j++ )
            col[j] += a[i][j];
    }
}
ifstream fin ( "elimin.in" );
ofstream fout ( "elimin.out" );
int main() {
    int i, j, aux;
    fin >> n >> m >> r >> c;

    if ( n < m ) {
        for ( i = 0; i < n; i++ )
            for ( j = 0; j < m; j++ )
                fin >> a[i][j];
    } else {
        for ( i = 0; i < n; i++ )
            for ( j = 0; j < m; j++ )
                fin >> a[j][i];
        aux = n, n = m, m = aux;
        aux = r, r = c, c = aux;
    }

    for ( i = 0; i < m; i++ )
        ord[i] = i;

    for ( i = 0; i < n; i++ )
        for ( j = 0; j < m; j++ )
            col[j] += a[i][j];
    st[0] = -1;
    bkt ( 1 ); // nu am facut cu descompunerea in baza 2 deoarece
    // trebuia sa verificam pt fiecare indice nr de biti 1
    fout << maxy;

    return 0;
}