Cod sursa(job #1142027)

Utilizator andreiagAndrei Galusca andreiag Data 13 martie 2014 13:16:48
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>

using namespace std;
const int Mmax = 16;
const int Nmax = 10000;

int tb[Mmax][Nmax];
int v[Nmax];
int N, M, R, C;

inline int bits(int m)
{
    int ret = 0;
    while (m) {
        m = m & (m-1);
        ret++;
    }
    return ret;
}

int main()
{
    ifstream f ("elimin.in");
    ofstream g ("elimin.out");

    f >> M >> N >> R >> C;

    int t = 0, x;
    if (M > N) t = 1;

    for (int i = 0; i < M; i++)
    for (int j = 0; j < N; j++)
    {
        f >> x;
        if (t) tb[j][i] = x;
        else tb[i][j] = x;
    }

    if (t) {
        x = M; M = N; N = x;
        x = R; R = C; C = x;
    }

    int best = 0;
    for (int m = 0; m < (1 << M); m++)
        if(bits(m) == R) {
            memset(v, 0, sizeof(v));
            for (int i = 0; i < M; i++) {
                if (m & (1 << i)) continue;
                for (int j = 0; j < N; j++)
                    v[j] += tb[i][j];
            }
            sort(v, v+N);

            int sum = 0;
            for (int i = C; i < N; i++)
                sum += v[i];
            if (sum > best) best = sum;
        }

    g << best << endl;

    return 0;
}