Cod sursa(job #10175)

Utilizator cos_minBondane Cosmin cos_min Data 27 ianuarie 2007 22:56:54
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <stdio.h>
#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

#define in "elimin.in"
#define out "elimin.out"

int maxim=-1;
vector< vector<int> > v;
vector<int> x;
vector<int> linie; // suma de pe fiecare linie
vector<int> liniecst;
int n, m, r, c;
long long t=0;
long long ok,ok2;

int Ok(int);
void Write(int);
void Back(int);
void ReadData(); 

int main()
{
    ReadData();
    
    return 0;
}

void ReadData()
{
     freopen(in,"r",stdin);
     freopen(out,"w",stdout);
     
     scanf("%d%d%d%d",&m,&n,&r,&c);
     
     v.resize(m+1);
     x.resize(n+1);
     linie.resize(m+1);
     liniecst.resize(m+1);
     for ( int i = 1; i <= m; i++ )
         v[i].resize(n+1);
     
     for ( int i = 1; i <= m; i++ )
     {
         linie[i] = 0;
         liniecst[i] = 0;
         for ( int j = 1; j <= n; j++ )
         {
             scanf("%d",&v[i][j]);
             linie[i] += v[i][j];
             liniecst[i] += v[i][j];
         }
     }
     ok = 1;
     ok2 = 1;
     x[0] = 1;
     
     if ( c == 0 && r == 0 )
     {
          maxim = 0;
          for ( int i = 1; i <= m; i++ )
              maxim += linie[i];
          
          printf("%d",maxim);
          exit(0);
     }
     else if ( c == 0 )
     {
          maxim = 0;
          sort(linie.begin(),linie.end() );
      
          for ( int i = r+1; i <= m; i++ )
          {
              maxim += linie[i];
          }
          printf("%d",maxim);
          exit(0);
          
      }
      if ( r == 0 ) r -= 1;
           
     for ( int i = 0; i <= c; i++ )
     {
         ok *= (n-c+i);
        // printf("%d\n", n-c+i);
         if ( i > 0 ) ok2 *= i;
     }
     
     ok = ok / ok2; 
   //  printf("%d ",ok);   
         
     Back(1);
     printf("%d",maxim);
}           

void Back(int k)
{
     for ( int i = x[k-1]; i <= n; i++ )  
     {
         x[k] = i;
         if ( Ok(k) )
         {
              if ( k == c ) Write(k);
              else if ( k < c ) Back(k+1);
         }
     }
}

int Ok(int k)
{
    for ( int i = 1; i < k; i++ )
        if ( x[i] == x[k] ) return 0;
    return 1;
}

void Write(int k)
{     
      int sum=0;
      t+=1;
      
    /*  for ( int i = 1; i <= m; i++ )
      {
          linie[i] = 0;
          for ( int j = 1; j <= n; j++ )
              linie[i] += v[i][j];
      }*/
      
    /*  for ( int j = 1; j <= k; j++ )
          printf("%d ", x[j]);
      
      printf("\n");*/
      
     /* for ( int i = 1; i <= m; i++ )
          for ( int j = 1; j <= k; j++ )
          {
              linie[i] -= v[i][x[j]];
          }*/
     for ( int i = 1; i <= m; i++ )
     {
         linie[i] = liniecst[i];
         for ( int j = 1; j <= k; j++ )
         {
             linie[i] -= v[i][x[j]];
         }
     }
      
      sort(linie.begin(),linie.end() );
      
      for ( int i = r+1; i <= m; i++ )
      {
         // printf("%d ",linie[i]);
          sum += linie[i];
      }
     // printf("\n");
          
      if ( sum > maxim ) maxim = sum;
     // if ( t == ok+2 ) printf("%lld", maxim), exit(0);
}