Cod sursa(job #2312736)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 5 ianuarie 2019 14:20:23
Problema Elimin Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

long long m, n, r, c, **v, sc, *VectorS, *sol, rez;

bool cmp ( long long a, long long b)
{
    if ( a <= b )
        return true;
    return false;
}

void Suma( )
{
    long long i, j;
    sc = 0;
    for ( i = 1; i <= m; i++ )
        VectorS[i] = 0;
    for ( i = 1; i <= n - r; i++)
        for ( j = 1; j <= m; j++ )
            VectorS[j] += v[sol[i]][j];
    sort( VectorS + 1, VectorS + m + 1, cmp);
    for ( i = m ;i > c; i-- )
        sc += VectorS[i];
    if ( sc > rez )
        rez = sc;
}

void bkt ( long long k )
{
    long long i;
    for ( i = sol[k - 1] + 1 ; i <= n; i++ )
    {
        sol[k] = i;
        if( k == n - r )
            Suma();
        else bkt( k + 1 );
    }
}

int main()
{
    long long i, j;

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

    in >> n >> m >> r >> c;

    if (n > m)
    {
        n = n + m;
        m = n - m;
        n = n - m;
        r = r + c;
        c = r - c;
        r = r - c;
    }

    v = new long long * [n + 1];
    VectorS = new long long [m + 1];
    sol = new long long [m + 1];
    for ( i = 1; i <= n; i++)
    {
        v[i] = new long long [m + 1];
        for ( j = 1; j <= m; j++ )
            in >> v[i][j];
    }

    bkt ( 1 );

    out << rez;

    for ( i = 1; i <= n; i++ )
        delete( v[i] );
    delete ( v );
    delete ( VectorS );
    delete ( sol );

    in.close();
    out.close();

    return 0;
}