Cod sursa(job #852600)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 11 ianuarie 2013 14:50:01
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 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;
}