Cod sursa(job #1333452)

Utilizator wGEORGEWGeorge Cioti wGEORGEW Data 3 februarie 2015 10:40:51
Problema Elimin Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#define DIM 5005
#define INF 100002
using namespace std;
 
ifstream fin("elimin.in");
ofstream fout("elimin.out");
int D[DIM][DIM],N,M,R,C,s[DIM],maxim,b[INF],a[DIM];
int main(){
    for(int i=1;i<INF;i++)
        b[i]=b[i/2]+i%2;
    fin>>N>>M>>R>>C;
    if(M>N){
        swap(N,M);
        swap(R,C);
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++){
            fin>>D[i][j];
            a[i]=a[i]+D[i][j];
        }
    for(int k=1;k<=(1<<M)-1;k++)
        if(b[k]==C)
            {
 
                memcpy(s,a,sizeof(a));
                for(int i=1;i<=N;i++){
                    for(int j=1;j<=M;j++)
                        if(k&(1<<(j-1)))
                            s[i]-=D[i][j];
                }
                sort(s+1,s+N+1);
                unsigned long long sum=0;
                for(int j=R+1;j<=N;j++)
                    sum+=s[j];
                if(sum>maxim)
                    maxim=sum;
            }
    fout<<maxim;
    fin.close();fout.close();
    return 0;
}