Cod sursa(job #2533001)

Utilizator NoemikulcsarKulcsar Noemi Noemikulcsar Data 28 ianuarie 2020 17:51:50
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <algorithm>
#define lim 600
using namespace std;
ifstream cin("elimin.in");
ofstream cout("elimin.out");
int n,m;
int sl[lim],sc[lim],r,cc,ult[lim],ans=-32000*86,nv[lim],st,c[lim][lim];
void backt(int lvl)
{
    if(lvl==r)
    {
        for (int i=1;i<=m;++i)
            nv[i]=sc[i];
        sort(nv+1,nv+m+1);
        int s=0;
        for(int i=m;i>cc;--i)
            s+=nv[i];
        ans=max(ans,s);
    }
    else
    {   for(int j=ult[lvl]+1;j<=n;++j){
        for(int i=1;i<=m;++i)
            sc[i]-=c[j][i];
            ult[lvl+1]=j;
            backt(lvl+1);
            for(int i=1;i<=m;++i)
                sc[i]+=c[j][i];
    }
    }
}
int main()
{
    int i,j,mat;
    cin>>n>>m>>r>>cc;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {   cin>>mat;
            st+=mat;
            c[i][j]=mat;
          //  sl[i]+=mat;
          //  sc[j]+=mat;
        }
        if(n>m)
        {
         for(i=1;i<=n;++i)
            for(j=1;j<i;++j){
            swap(c[i][j],c[j][i]);
           // sc[i]+=c[n-j+1][i];
           // sl[n-j+1]+=c[n-j+1][i];
            }
        swap(n,m);
        swap(r,cc);
        for(i=1;i<=n;++i){
            for(j=1;j<=m;++j)
            sc[j]+=c[i][j],sl[i]+=c[i][j];
        }
          backt(0);
        }
        else
        {   for(i=1;i<=n;++i){
            for(j=1;j<=m;++j)
            sc[j]+=c[i][j],sl[i]+=c[i][j];
        }
            backt(0);
        }
        cout<<ans;
    return 0;
}