Cod sursa(job #1804775)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 12 noiembrie 2016 22:51:39
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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;
    for(i=0;i<M;++i)
        for(j=0;j<N;++j)
            if(M<N) f>>A[i][j];
            else f>>A[j][i];
    if(M>=N)
    {
        swap(M,N);
        swap(R,C);
    }
    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;
}