Cod sursa(job #1972899)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 23 aprilie 2017 21:40:51
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("elimin.in");
ofstream out("elimin.out");
int v[20],w[1001],maxim,m,n,mat[530][530],l,c,x,y,da,hz[20];
void back1(int p, int k,int h ){
    int a,b,i,ok,s,sum,g;
    if( p == k+1 ){
        g = 0;
        for( b = 1; b <= m; b ++ ){
            s = 0;
            for( a = 1; a <= n; a++ ){
                ok =1;
                for( i = 1; i <= k; i ++ ){
                    if( a == v[i] ){
                        ok = 0;
                    }
                }
                if( ok == 1 ){
                    s+=mat[a][b];
                }
            }
            g++;
            w[g] = s;
        }
        sum = 0;
        sort( w + 1, w + g +1 );
        for( i = c+1; i <= g ; i ++ ){
            sum+=w[i];
        }
        if( sum > maxim ){
            maxim = sum;
        }
    }
    else{
        for( i = v[p-1] + 1; i <= h; i ++ ){
            v[p]= i ;
            back1(p+1,k,h);
        }
    }
    return;

}
void back2(int p, int k,int h ){
    int a,b,i,ok,s,sum,g;
    if( p == k+1 ){
        g = 0;
        for( b = 1; b <= n; b ++ ){
            s = 0;
            for( a = 1; a <= m; a ++ ){
                ok =1;
                for( i = 1; i <= k; i ++ ){
                    if( a == v[i] ){
                        ok = 0;
                    }
                }
                if( ok == 1 ){
                    s+=mat[b][a];
                }
            }
            g++;
            w[g] = s;
        }
        sort( w + 1, w + g +1 );
        sum =0;
        for( i = l+1; i <= g ; i ++ ){
            sum+=w[i];
        }

        if( sum > maxim ){
            maxim = sum;
        }
    }
    else{
        for( i = v[p-1] + 1; i <= h; i ++ ){
            v[p]=i;
            back2(p+1,k,h);
        }
    }
    return ;
}
int main(){
    in >> n >> m;
    in >> l >> c;
    for( x = 1; x <= n; x ++ ){
        for( y = 1; y <= m; y ++ ){
            in >> mat[x][y];
        }
    }
    if( m > n){
       back1( 1,l,n);
    }
    else{
         back2(1,c,m);
    }
    out<<maxim;
    return 0;
}