Cod sursa(job #3219512)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 31 martie 2024 16:02:28
Problema Elimin Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
using namespace std;
ifstream cin("elimin.in");
ofstream cout("elimin.out");
int n,m,L,C,x[7300],y[7300],a[7300][7300];
bool frl[7300],frc[7300];
long long Max,sum,sl[7300],sc[7300],total;
long long sol(){
    long long s=sum;
    for(int i=1;i<=L;i++)
        for(int j=1;j<=C;j++)
            s+=a[x[i]][y[j]];
    return s;
}
void coloane(int k){
    if(k==C+1){
        long long s=sol();
        if(s>Max)
            Max=s;
    }else{
        for(int i=y[k-1]+1;i<=m;i++){
            y[k]=i;
            frc[i]=1;
            sum-=sc[i];
            coloane(k+1);
            sum+=sc[i];
            frc[i]=0;
        }
    }
}
void lini(int k){
    if(k==L+1){
        coloane(1);
    }else{
        for(int i=x[k-1]+1;i<=n;i++){
            x[k]=i;
            frl[i]=1;
            sum-=sl[i];
            lini(k+1);
            sum+=sl[i];
            frl[i]=0;
        }
    }
}
int main()
{
    cin>>n>>m>>L>>C;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            sl[i]+=a[i][j];
            sc[j]+=a[i][j];
            sum+=a[i][j];
        }
    lini(1);
    cout<<Max;
    return 0;
}