Cod sursa(job #2502678)

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

using namespace std;

int mat[21][8001];
bool lin[21];
int col[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 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;
        s=0;
        for (int j=1;j<=m;j++)
        {
          sum=0;
          for (int l=1;l<=n;l++)
                if (!lin[l])
                  sum+=mat[l][j],s+=mat[l][j];
          col[j]=sum;
        }
        sort(col+1,col+m+1);
        for (int j=1;j<=c;j++)
            s-=col[j];
        max1=max(max1,s);
      }
    }
    out<<max1;
    return 0;
}