Cod sursa(job #3315078)

Utilizator alexalghisiAlghisi Alessandro meitatiidirect.ro alexalghisi Data 12 octombrie 2025 11:47:25
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

int n,m,a[555][555],rez,r,c;
vector<int>x;

void procesare1(){
    vector<bool>t(n+1,false);
    for(int i=1;i<=r;i++) t[x[i]]=1;
    int sum=0;
    vector<int>sc;
    for(int j=1;j<=m;j++){
        int csum=0;
        for(int i=1;i<=n;i++){
            if(!t[i]) csum+=a[i][j];
        }
        sc.push_back(csum);
    }
    sort(sc.begin(),sc.end());
    for(int i=c;i<sc.size();i++) sum+=sc[i];
    rez=max(rez,sum);
}

void back1(int step){
    if(step>r){
        procesare1();
        return;
    }
    for(int i=x[step-1]+1;i<=n-r+step;i++){
        x[step]=i;
        back1(step+1);
    }
}

void procesare2(){
    vector<bool>t(m+1,false);
    for(int i=1;i<=c;i++)t[x[i]]=1;
    int sum=0;
    vector<int> sc;
    for(int i=1;i<=n;i++){
        int csum=0;
        for(int j=1;j<=m;j++){
            if(!t[j]) csum+=a[i][j];
        }
        sc.push_back(csum);
    }
    sort(sc.begin(),sc.end());
    for(int i=r;i<sc.size();i++) sum+=sc[i];
    rez=max(rez,sum);
}

void back2(int step){
    if(step>c){
        procesare2();
        return;
    }
    for(int i=x[step-1]+1;i<=m-c+step;i++){
        x[step]=i;
        back2(step+1);
    }
}

int main(){
    fin>>n>>m>>r>>c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fin>>a[i][j];
        }
    }
    if(n<=m){
        x.resize(n+1);
        back1(1);
        fout<<rez;
    }else{
        x.resize(m+1);
        back2(1);
        fout<<rez;
    }
    return 0;
}