Cod sursa(job #1098166)

Utilizator andrettiAndretti Naiden andretti Data 4 februarie 2014 16:25:56
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define maxn 7300
using namespace std;

int ok,n,m,R,C,sol=-1;
int x[maxn],s[maxn];
vector<int> a[maxn];

void read()
{
    int x;
    scanf("%d%d%d%d",&n,&m,&R,&C);

    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      scanf("%d",&x),a[i].pb(x);
}

int detR()
{
    int Cval,sum=0,c;
    for(int i=1;i<=m;i++)
    {
        s[i]=0;
        for(int j=1;j<=n;j++)
         if(x[j]) s[i]+=a[j][i-1];
        sum+=s[i];
    }
    nth_element(s+1,s+C,s+m+1); Cval=s[C]; c=C;
    for(int i=1;i<=m;i++) if(s[i]<Cval) sum-=s[i],c--;
    sum-=(Cval*c);
    return sum;
}

int detC()
{
    int Rval,sum=0,r;
    for(int i=1;i<=n;i++)
    {
        s[i]=0;
        for(unsigned int j=0;j<a[i].size();j++)
         if(x[j+1]) s[i]+=a[i][j];
        sum+=s[i];
    }
    nth_element(s+1,s+R,s+n+1); Rval=s[R]; r=R;
    for(int i=1;i<=n;i++) if(s[i]<Rval) sum-=s[i],r--;
    sum-=(Rval*r);
    return sum;
}

void backR(int k,int nr)
{
    if(k>n && nr==R){sol=max(sol,detR()); return;}
    if(k>n) return;
    x[k]=1; backR(k+1,nr);
    if(nr==R) return;
    x[k]=0; backR(k+1,nr+1);
}

void backC(int k,int nr)
{
    if(k>m && nr==C){sol=max(sol,detC()); return;}
    if(k>m) return;
    x[k]=1; backC(k+1,nr);
    if(nr==C) return;
    x[k]=0; backC(k+1,nr+1);
}

void solve()
{
    if(n<=m) backR(1,0);
    else backC(1,0);
}

int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);

    read();
    solve();
    printf("%d",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}