Cod sursa(job #58008)

Utilizator RazvanSSavu Razvan RazvanS Data 3 mai 2007 21:37:40
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 600

using namespace std;

int M[MAX][MAX];
int m, n, r, c;
int smax;
//int V[MAX];
int S[MAX];

/*
     
void sch(int x, int y)
    {int aux;
     aux=S[x], S[x]=S[y];  S[y]=aux;}   
     
int pivot(int p, int q)
    {
     while(p<q) {
                while(p<q && S[p]>=S[q]) p++;
                if(p<q) sch(p, q);
                while(p<q && S[p]>=S[q]) q--;
                if(p<q) sch(p, q);
                }
     
     return p;
     }                  
     
void sort (int p, int q)
     {int k;
      if(p<q) {k=pivot(p, q);
               sort(p, k-1);
               sort(k+1, q);
              }
     }
                     
*/     

     
int main( void )
        {
         freopen("elimin.in", "r", stdin);
          scanf("%d %d %d %d\n", &m, &n, &r, &c);
          int i, j, aux;
          if(n<=15) { for(i=1;i<=m;++i)
                     for(j=1;j<=n;++j)
                          scanf("%d ", &M[i][j]);
                }
                
                else { for(i=1;i<=m;++i)
                   for(j=1;j<=n;++j)
                       scanf("%d ", &M[j][i]);
                 
                aux=m;
                m=n;
                n=aux;
                aux=c;
                c=r;
                r=aux;
                }
          freopen("elimin.out", "w", stdout);
          int P = 1<<n, Q= 1<< (n-1);
     
     int nr;
     
     int s, t, stop;
     for(i=(1<<c)-1;i< P; ++i)
         {
          for(j=Q, stop=0, s=0, nr=0; j!=0; j>>=1)
             {if(i&j)  nr++;
              
             }
                             
          if(nr!=c) stop=1;
          if(!stop) {
                     for(j=1;j<=m;++j) //printf("* %d\n", S[j-1]))
                        for(t=1,S[j-1]=0, nr=Q;t<=n;++t, nr>>=1)
                               S[j-1]+=M[j][t]*!(nr&i);
                           
                      sort(S, S+m);     
                     
                     for(j=m-1;j>r-1;--j)
                         s+=S[j];
                     if(s>smax) smax=s;
                    }
          }            
         printf("%d\n", smax);
         
         
         
         return 0;
         }