Cod sursa(job #2502689)

Utilizator sygAndreiIonitaIonita Andrei sygAndreiIonita Data 1 decembrie 2019 13:57:40
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#pragma GCC optimize("O3")
#include <fstream>
#include <algorithm>

using namespace std;

int mat[21][8001];
bool lin[21];
int col[8001],col1[8001];

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

int main()
{
    ios::sync_with_stdio(false);
    int n,m,max1=-100000000,r,c,sum,s;
    in>>n>>m>>r>>c;
    if (n<=m)
        for (int i=1; i<=n; i++)
            for (int j=1; j<=m; j++)
                in>>mat[i][j];
    else
    {
        for (int i=1; i<=n; i++)
            for (int j=1; j<=m; j++)
                in>>mat[j][i];
        swap(n,m);
        swap(r,c);
    }
    for (int j=1; j<=m; j++)
        for(int i=1; i<=n; i++)
            col1[j]+=mat[i][j];
    for (int i=0; i<(1<<n); ++i)
    {
        if (__builtin_popcount(i)==r)
        {
            for (int j=1; j<=20; j++)
                lin[j]=0;
            for (int j=1; j<=n; j++)
                if (i&(1<<(j-1)))
                    lin[j]=1;
            for (int j=1; j<=m; j++)
            {
                col[j]=col1[j];
                for (int l=1; l<=n; l++)
                    if (lin[l])
                        col[j]-=mat[l][j];
            }
            sort(col+1,col+m+1);
            s=0;
            for (int j=c+1; j<=m; j++)
                s+=col[j];
            max1=max(max1,s);
        }
    }
    out<<max1;
    return 0;
}