Cod sursa(job #1237753)

Utilizator apopeid15Apopei Daniel apopeid15 Data 4 octombrie 2014 19:21:53
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <algorithm>
#include <fstream>
  
using namespace std;
  
ifstream fin("elimin.in");
ofstream fout("elimin.out");
  
const int inf= 1<<30;
const int nmax= 20;
const int mmax= 8000;
  
int a[nmax+1][mmax+1];
int n= 0, m= 0, l= 0, c= 0, sol= -inf;
  
int s[mmax+1], u[nmax+1];
  
void back( int x, int last ) {
    if ( x==l+1 ) {
        for ( int i= 1; i<=n; ++i ) {
            for ( int j= 1; j<=m; ++j ) {
                s[j]+= a[i][j]*((u[i]+1)%2);
            }
        }
        sort(s+1, s+m+1);
          
        int sum= 0;
        for ( int i= m; i>c; --i ) {
            sum+= s[i];
        }
        if ( sum>sol ) {
            sol= sum;
        }
        for ( int i= 1; i<=m; ++i ) {
            s[i]= 0;
        }
    } else {
        for ( int i= last+1; i<=n; ++i ) {
            u[i]= 1;
            back(x+1, i);
            u[i]= 0;
        }
    }
}
  
int main(  ) {
    fin>>n>>m>>l>>c;
    if ( n>nmax ) {
        for ( int i= 1; i<=n; ++i ) {
            for ( int j= 1; j<=m; ++j ) {
                fin>>a[j][i];
            }
        }
 
        swap(n, m), swap(l, c);
    }
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            fin>>a[i][j];
        }
    }
      
    back(1, 0);
  
    fout<<sol<<"\n";
  
    return 0;
}