Cod sursa(job #1021311)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 3 noiembrie 2013 17:27:46
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define lim 1000000
#define Next ++position == lim?f.read(buffer, lim), position = 0:0

using namespace std;

ifstream f("elimin.in");
int position;
int st[18];
char buffer[lim];
int n, m, r, c, answer;
int sumc[7300];
int a[18][7300];

inline void Read(int &x)
{
    for (; buffer[position] < '0' || buffer[position] > '9'; Next);
    for (x = 0; '0' <= buffer[position] && buffer[position] <= '9'; x = x*10 + buffer[position]-'0', Next);
}

void Read()
{
    Read(n), Read(m), Read(r), Read(c);
    if (n<=m)
    {
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=m; ++j)
                Read(a[i][j]);
    }
    else
    {
        for (int i = 1; i<=n; ++i)
            for (int j=1; j<=m; ++j)
                Read(a[j][i]);
        swap(n, m), swap(r, c);
    }
    f.close();
}

inline void Actualizare()
{
    int aux_sumc[7300];
    int i, j;
    for (i=1; i<=m; ++i)
    {
        aux_sumc[i] = sumc[i];
        for (j=1; j<=r; ++j)
            aux_sumc[i] -= a[st[j]][i];
    }
    sort(aux_sumc+1, aux_sumc+m+1);
    int sum = 0;
    for (i=m; i>c; --i)
        sum += aux_sumc[i];
    answer = max(answer, sum);
}


inline void back(int k)
{
    if (k == r+1)
        Actualizare();
    else
    {
        for (int i = st[k-1]+1; i<=n-r+k; ++i)
        {
            st[k] = i;
            back(k+1);
        }
    }
}

void CreateSumc()
{
    for (int i = 1; i<=n; ++i)
        for (int j=1; j<=m; ++j)
            sumc[j] = sumc[j] + a[i][j];
}

void Solve()
{
    CreateSumc();
    /// combinari de n luate cate r
    back(1);
}

void Write()
{
    ofstream g("elimin.out");
    g<<answer<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}