Cod sursa(job #1751553)

Utilizator stefanchistefan chiper stefanchi Data 1 septembrie 2016 15:50:48
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int m,n,r,c;
int mat[88][3700];
int suma_coloana[3700];
int combinari[88];
int suma_maxima = -1;
int suma_curenta;
bool linie_taiata[88];
int nr;

void read()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    scanf("%d %d %d %d ",&m,&n,&r,&c);
    if(n < m)
    {
        for(int j = 0 ; j < n ; j++)
            for(int i = 0 ; i < m ; i++)
                scanf("%d ",&mat[i][j]);
        swap(m,n);
        swap(r,c);
    }
    else
    {
        for(int i = 0 ; i < m ; i++)
            for(int j = 0 ; j <  n  ; j++)
                scanf("%d",&mat[i][j]);
    }
}

void reset()
{
    for(int i = 0 ; i < m ; i++)
        linie_taiata[i] = false;
    for(int j = 0 ; j < n ; j++)
        suma_coloana[j] = 0;
}

void suma()
{
    suma_curenta = 0;
    int k = 0;
    for(int i = 0 ; i < m; i++)
    {
        if(combinari[k] - 1 == i)
            {
                k++;
                continue;
            }
        else
        {
            for(int j = 0 ; j < n ; j++)
                suma_coloana[j] += mat[i][j];
        }
    }
    sort(suma_coloana,suma_coloana + n);
    for(int i = c ; i < n ; i++)
        suma_curenta += suma_coloana[i];
    if(suma_curenta > suma_maxima)
        suma_maxima = suma_curenta;
    reset();
}

void rezolv()
{
    for(int i = 0 ; i < r ; i++)
        combinari[i]= i + 1;
    int i = r - 1;
    int dif = 0;
    int pozitie = i;
    while(i > -1)
    {
        if(combinari[i] == m - dif)
        {
            dif++;
            pozitie = i;
            i--;
            continue;
        }
        if( i < pozitie)
        {
            suma();
            combinari[i]++;
            i++;
            for( i ; i < r ; i++)
                combinari[i] = combinari[i - 1] + 1;
            dif = 0;
            i--;
            pozitie = i;

            continue;
        }
        if( combinari[i] < n - dif)
        {
            suma();
            combinari[i]++;
            continue;
        }
    }
    suma();
    printf("%d",suma_maxima);
}

int main()
{
    read();
    rezolv();
    return 0;
}