Cod sursa(job #1680565)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 8 aprilie 2016 21:18:41
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#include <algorithm>
using namespace std;

FILE *in, *out;

const int M_max = 20;
const int N_max = 7300;

int A[M_max][N_max];

int sol[M_max];

int s[N_max];

bool GASIT;
int Max;

int M, N, R, C;

inline void read()
{
    int i, j;

    fscanf(in, "%d %d", &M, &N);
    fscanf(in, "%d %d", &R, &C);

    if(M <= N)
        for(i = 1; i <= M; i++)
            for(j = 1; j <= N; j++) fscanf(in, "%d", &A[i][j]);
    else
    {
        swap(M, N);
        swap(R, C);

        for(j = 1; j <= N; j++)
            for(i = 1; i <= M; i++) fscanf(in, "%d", &A[i][j]);
    }
}

inline void prelucrare()
{
    int i, j, k, S = 0;

    for(j = 1; j <= N; j++) s[j] = 0;

    for(j = 1; j <= N; j++)
    {
        k = 1;

        for(i = 1; i <= M; i++)
        {
            if(i != sol[k])
                s[j] += A[i][j];
            else
                k++;
        }
    }

    sort(s + 1, s + N + 1);

    for(j = C + 1; j <= N; j++) S += s[j];

    if(!GASIT)
    {
        Max = S;
        GASIT = true;
    }
    else
        if(Max < S) Max = S;
}

inline void bkt(int p)
{
    if(p - 1 == R) prelucrare();
    else
        for(int i = 1 + sol[p - 1]; i <= M - R + p; i++)
        {
            sol[p] = i;
            bkt(p + 1);
        }
}

int main()
{
    in = fopen("elimin.in", "r");
    out = fopen("elimin.out", "w");

    read();
    bkt(1); /* COMBINARI DE M LUATE CATE R */

    fprintf(out, "%d", Max);

    return 0;
}