Cod sursa(job #1804774)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 12 noiembrie 2016 22:48:33
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("elimin.in");
ofstream g("elimin.out");
int M,N,R,C,t,i,j,ans,total_sum,Col[1<<13],ord[1<<13],A[20][1<<13],rem[1<<13];
inline bool cmp(int a,int b)
{
    return Col[a]<Col[b];
}
void back(int k)
{
    if(k>R)
    {
        int _s=0;
        nth_element(ord,ord+C,ord+N,cmp);
        for(int j=0;j<N;++j) _s+=Col[j];
        for(int j=0;j<C;++j) _s-=Col[ord[j]];
        ans=max(ans,_s);
    }
    else
        for(int i=rem[k-1]+1;i<=M;++i)
        {
            rem[k]=i;
            for(int j=0;j<N;++j) Col[j]-=A[rem[k]-1][j];
            back(k+1);
            for(int j=0;j<N;++j) Col[j]+=A[rem[k]-1][j];
        }
}
int main()
{
    f>>M>>N>>R>>C;
    if(M>N)
    {
        swap(M, N);
        swap(R, C);
    }
    for(i=0;i<M;++i)
        for(j=0;j<N;++j) f>>A[i][j];
    for(j=0;j<N;++j) ord[j]=j;
    for(i=0;i<M;++i)
        for(j=0;j<N;++j)
        {
            Col[j]+=A[i][j];
            total_sum+=A[i][j];
        }
    back(1);
    g<<ans;
    return 0;
}