Cod sursa(job #10403)

Utilizator cos_minBondane Cosmin cos_min Data 28 ianuarie 2007 13:41:00
Problema Elimin Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <stdio.h>
#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <set>
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;
multiset<long long> p;
multiset<long long>::iterator it;
int n, m, r, c;
long long t=0;
long long ok,ok2;

int Ok(int);
void Write(int);
void Back(int);
void ReadData(); 
//void Qsort(int,int);

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() );
        //  Qsort(1,n);
      
          for ( int i = r+1; i <= m; i++ )
          {
              maxim += linie[i];
          }
          printf("%d",maxim);
          exit(0);
          
      }
      if ( r == 0 ) r -= 1;
           
     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;
      long long val;
      
    /*  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]];
          }*/
     p.clear();
     for ( int i = 1; i <= m; i++ )
     {
         val = liniecst[i];
         for ( int j = 1; j <= k; j++ )
         {
             val -= v[i][x[j]];
         }
         p.insert(val);
     }
      
     // sort(linie.begin(),linie.end() );
    //  Qsort(1,n);
      
      it = p.begin();
      int q =0;
      while ( q != r ) ++it, q++;
      
      while ( it != p.end() )
      {
          sum += *it;
          it++;
      }
     // printf("\n");
          
      if ( sum > maxim ) maxim = sum;
     // if ( t == ok+2 ) printf("%lld", maxim), exit(0);
}