Cod sursa(job #3353829)

Utilizator wizardragonWizard Dragon wizardragon Data 12 mai 2026 03:00:36
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 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);
  }
  vector<bool> keep(n,0);
  vector<int> s(m,0),s2(m,0);
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      s[j]+=a[i][j];
    }
  }
  int sol=0;
  function<void(int,int)>bkt=[&](int row,int dlt){
    if(dlt+n-row<rr){
      return;
    }
    if(row==n){
      for(int c=0;c<m;c++){
        s2[c]=s[c];
      }
      sort(s2.rbegin(),s2.rend());
      int now=0;
      for(int i=0;i<m-cc;i++){
        now+=s2[i];
      }
      sol=max(sol,now);
      return;
    }
    keep[row]=1;
    bkt(row+1,dlt);
    if(dlt+1<=rr){
      keep[row]=0;
      for(int c=0;c<m;c++) {
        s[c]-=a[row][c];
      }
      bkt(row+1,dlt+1);
      for(int c=0;c<m;c++) {
        s[c]+=a[row][c];
      }
    }
  };
  bkt(0,0);
  cout<<sol<<"\n";
  return 0;
}