Cod sursa(job #1002990)

Utilizator robert_stefanRobert Stefan robert_stefan Data 29 septembrie 2013 15:31:46
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <limits.h>
#define IN "elimin.in"
#define OUT "elimin.out"
 
using namespace std;
 
ifstream in(IN);
ofstream out(OUT);
 
int r, c, sol[7300], sc[7300], sl[7300], sc2[7300], soll, n, m;
int a[500][500];
long long sumtot, mx=-2147000000;
 
inline void read()
{
    in>>n>>m>>r>>c;
    int i, j;
    if(n<=m)
        for(i=1; i<=n; ++i)
            for(j=1; j<=m; ++j)
                in>>a[i][j];
    else
    {
        for(i=1; i<=n; ++i)
            for(j=1; j<=m; ++j)
                in>>a[j][i];
        swap(n,m);
        swap(r,c);
    }
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            sl[i]+=a[i][j];
                sc[j]+=a[i][j];
            sumtot+=a[i][j];
            }
}
 
inline void solution()
{
    int i, j;
    soll=sumtot;
     
    for(i=1; i<=m; ++i)
        sc2[i]=sc[i];
    for(i=1; i<=r; ++i)
    {
        for(j=1; j<=m; ++j)
            sc2[j]-=a[sol[i]][j];
        soll-=sl[sol[i]];
    }
    if(c)
    {
        nth_element(sc2+1,sc2+c,sc2+m+1);
        for(i=1; i<=c; ++i)
            soll-=sc2[i];
    }
    if(soll>mx)
        mx=soll;
}
 
inline void write(int lim)
{
    for(int i=1; i<=lim; ++i)
        out<<sol[i]<<' ';
    out<<'\n';
}
 
inline void BT(int k)
{
    if(k==r+1)
    {
        solution();
    }
    else
    {
        sol[k]=sol[k-1];
        while(sol[k]<n)
        {
            ++sol[k];
            BT(k+1);
        }
    }
}
 
int main()
{
    read();
    BT(1);
    out<<mx;
    in.close();
    out.close();
    return 0;
}