Cod sursa(job #1748002)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 25 august 2016 21:56:30
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int m, n, r, c, s[7500][20], sol[7500], sumaMax, sum[7500];

void citire()
{
    scanf("%d %d %d %d\n", &m, &n, &r, &c);
    if(n>=m)
    {
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                scanf("%d ", &s[i][j]);
    }
    else
    {
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                scanf("%d ", &s[j][i]);
        swap(m, n);
        swap(r, c);
    }
}

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

void rezolvareSuma()
{
    vectorReset();
    int sumaAjutor=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; ++j)
        {
            sum[i]+=s[i][j];
        }
        for(int j=1; j<=c; ++j)
        {
            sum[i]-=s[i][sol[j]];
        }
    }
    sort(sum+1, sum+n+1);
    for(int i=r+1; i<=n; ++i)
        sumaAjutor+=sum[i];
    sumaMax=max(sumaMax, sumaAjutor);
}
void back(int k)
{
    if(k==c+1)
    {
        rezolvareSuma();
        return;
    }
    for(int i=sol[k-1]+1; i<=m-r+k; ++i)
    {
        sol[k]=i;
        back(k+1);
    }
}
int main()
{
    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);
    citire();
    back(1);
    printf("%d", sumaMax);
    return 0;
}