Cod sursa(job #1745203)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 21 august 2016 14:31:23
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("elimin.in");
ofstream out("elimin.out");
const int maxn = 705;
int M[maxn][25];
int sum[maxn];
int n, m, r, c;
int v[25];
int mx;

void reset()
{
    for(int i = 1; i <= n; i++)
        sum[i] = 0;
}

int get_sum()
{
    reset();
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            sum[i] += M[i][j];
        for(int j = 1; j <= c; j++)
        {
            int col = v[j];
            sum[i] -= M[i][col];
        }
    }
    sort(sum + 1, sum + n + 1);
    int s = 0;
    for(int i = r + 1; i <= n; i++)
        s += sum[i];
    return s;
}

void _back_(int poz)
{
    if(m - v[poz - 1] < c)
        return;
    if(poz == c + 1)
    {
        mx = max(mx, get_sum());
        return;
    }
    for(int i = v[poz - 1] + 1; i <= n; i++)
    {
        v[poz] = i;
        _back_(poz + 1);
    }
}

int main()
{
    in >> n >> m >> r >> c;
    if(n >= m)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                in >> M[i][j];
    else
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                in >> M[j][i];
        swap(n, m);
        swap(r, c);
    }
    _back_(1);
    out << mx;
    return 0;
}