Cod sursa(job #2312754)

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

using namespace std;

const long long N = 5005;
long long m, n, r, c, sc, rez;
long long **v, *VectorS, *sol;
//long long v[N][N], sol[N],  VectorS[N];

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;
//        cout << sc << endl;
}

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;
//    cout <<" " << n << " " << m << " " << r << " " << c << endl;

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

//    cout <<" " << n << " " << m << " " << r << " " << c << endl;

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

    bkt ( 1 );

    out << rez;
//    cout << rez;

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

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

    return 0;
}