Cod sursa(job #3353827)

Utilizator wizardragonWizard Dragon wizardragon Data 12 mai 2026 02:57:16
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;

signed main() {
  freopen("elimin.in","r",stdin);
  freopen("elimin.out","w",stdout);
  int n,m,rr,cc;
  cin>>n>>m>>rr>>cc;
  vector<vector<int>> a;
  if(n<m){
    a.resize(n,vector<int>(m));
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++) {
        cin>>a[i][j];
      }
    }
  }else{
    a.resize(m,vector<int>(n));
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++) {
        cin>>a[j][i];
      }
    }
    swap(n,m);
    swap(rr,cc);
  }
  assert(n==(int)a.size());
  assert(m==(int)a[0].size());
  assert(n<=m);
  vector<bool> keep(n,0);
  vector<int> s(m,0);
  int sol=0;
  function<void(int,int)>bkt=[&](int row,int dlt){
    assert(dlt<=rr);
    if(row==n){
      if(dlt<rr){
        return;
      }
      assert(dlt==rr);
      for(int c=0;c<m;c++) {
        s[c]=0;
        for(int r=0;r<n;r++) {
          if(keep[r]){
            s[c]+=a[r][c];
          }
        }
      }
      sort(s.rbegin(),s.rend());
      int now=0;
      for(int i=0;i<m-cc;i++){
        now+=s[i];
      }
      sol=max(sol,now);
      return;
    }
    if(dlt+1<=rr){
      keep[row]=0;
      bkt(row+1,dlt+1);
    }
    keep[row]=1;
    bkt(row+1,dlt);
  };
  bkt(0,0);
  cout<<sol<<"\n";
  return 0;
}