Cod sursa(job #861719)

Utilizator stoicatheoFlirk Navok stoicatheo Data 21 ianuarie 2013 21:01:34
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<cstdio>
#include<cstring>
#include<cassert>
#include<algorithm>
using namespace std;
  
const int dim=801 ;
const int Dim=31 ;
  
int m,n,r,c,solutia,suma;
int a[dim][dim];
int v[Dim],s[dim];
  
void back(int x,int y){
    if(x == r+1){
          
        for(int i=1;i<=n;++i)
            if(v[i]){
                  
                for(int j=1;j<=m;++j){
                    s[j]+=a[i][j];
                      
                }
            }
        nth_element(s+1,s+c,s+1+m);
        for(int i=m;i>c;--i)
            suma+=s[i];
        if(suma > solutia)
            solutia = suma ;
        suma = 0 ;
        memset(s,0,sizeof(s));
        return;
    }  
    for(int i=y+1;i<=n-r+x;++i){
          
        v[i] = 0 ;
        back(x+1,i);
        v[i] = 1 ;
    }  
}
  
int main()
{
    assert(freopen("elimin.in","r",stdin));
    assert(freopen("elimin.out","w",stdout));
    assert(scanf("%d%d%d%d",&n,&m,&r,&c));
    if(n<=m){
          
        for(int i=1;i<=n;++i){
              
            for(int j=1;j<=m;++j)
                assert(scanf("%d",&a[i][j]));
            v[i] = 1;
        }
    }  
    else{
          
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                assert(scanf("%d",&a[j][i]));
        swap(m,n);
        swap(r,c);
    }  
    back(1,0);
    printf("%d\n",solutia);
    return 0;
}