Cod sursa(job #3362246)

Utilizator RobertIon013Ion Robert Andrei RobertIon013 Data 4 august 2026 18:55:42
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;
int K,L,M,N,R,C;
long long best;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    cin>>M>>N>>R>>C;
    K=M-R;
    L=N-C;
    vector<vector<int>> a(M,vector<int>(N));
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)cin>>a[i][j];
    if(N<M)
    {
        vector<vector<int>> b(N,vector<int>(M));
        for(int i=0;i<M;i++)
            for(int j=0;j<N;j++)b[j][i]=a[i][j];
        a.swap(b);
        swap(M,N);
        swap(R,C);
        K=M-R;
        L=N-C;
    }
    int totalMasks=1<<M;
    vector<long long> colSum(N);
    for(int mask=0;mask<totalMasks;mask++)
    {
        if(__builtin_popcount(mask)!=K)continue;
        fill(colSum.begin(),colSum.end(),0);
        for(int i=0;i<M;i++)
            if(mask&(1<<i))
                for(int j=0;j<N;j++)colSum[j]+=a[i][j];
        nth_element(colSum.begin(),colSum.begin()+L,colSum.end(),greater<long long>());
        long long sum=0;
        for(int j=0;j<L;j++)sum+=colSum[j];
        if(sum>best)best=sum;
    }
    cout<<best<<'\n';

    return 0;
}