Cod sursa(job #1693489)

Utilizator sucureiSucureiRobert sucurei Data 23 aprilie 2016 11:17:16
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#define MAXN 7300
#define DIM (1 << 13)

int N, M, R, C, A[32][MAXN];
int RSum[MAXN], LSum[MAXN], maxx, Tsum, minn = 0x3f3f3f3f;
int in[MAXN], pos = DIM, len;
char buf[DIM];

inline int r_int32(){
    while (buf[pos] < '0' || buf[pos] > '9'){
        if (++pos >= DIM) len = fread(buf, 1, DIM, stdin), pos = 0;
    }
    int val = 0;

    while (buf[pos] >= '0' && buf[pos] <= '9'){
        if (pos == len) break;
        val = val * 10 + buf[pos] - '0';
        if (++pos == DIM) len = fread(buf, 1, DIM, stdin), pos = 0;
    }
    return val;
}

inline void w_int32(int k){
    char lim[16], *s;
    s = lim + 15, *s = 0;

    do{
        *--s = k % 10 + '0';
        k /= 10;
    } while (k);
    puts(s);
}

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

    M = r_int32(), N = r_int32(), R = r_int32(), C = r_int32();

    if (M <= N){
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < N; ++j)
                A[i][j] = r_int32(),
                Tsum += A[i][j],
                LSum[i] += A[i][j],
                RSum[j] += A[i][j];
    }
    else {
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < N; ++j)
                A[j][i] = r_int32(),
                Tsum += A[j][i],
                LSum[j] += A[j][i],
                RSum[i] += A[j][i];
        R ^= C ^= R ^= C;
        M ^= N ^= M ^= N;
    }

    for (int i = 0; i < 1 << M; ++i){
        int x = i, j = 0, sum = 0;
        for (; x; x -= x & -x, ++j);
        if (j != R) continue;

        for (int j = 0; j < N; ++j) in[j] = RSum[j];

        for (int j = 0; j < M; ++j)
            if (i & (1 << j)){
                sum += LSum[j];
                for (int k = 0; k < N; ++k) in[k] -= A[j][k];
            }

        std::nth_element(in, in + C, in + N);
        for (int j = 0; j < C; ++j) sum += in[j];
        if (sum < minn) minn = sum;
    }

    w_int32(Tsum - minn);
    return 0;
}