Cod sursa(job #1751069)

Utilizator stefanchistefan chiper stefanchi Data 31 august 2016 18:02:33
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int m,n,r,c;
int mat[88][2000];
int suma_linie[88];
int suma_coloana[2000];
int combinari[88];
int suma_totala;
int suma_maxima;
int suma_curenta;
bool linie_taiata[88];
void read()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    scanf("%d %d %d %d ",&m,&n,&r,&c);
    if(n < m)
    {
        swap(n,m);
        swap(r,c);
        for(int i = 0 ; i < m ; i++)
            for(int j = 0 ; j < n ; j++)
            {
                scanf("%d ",&mat[i][j]);
                suma_linie[i] += mat[i][j];
            }
    }
    else
    {
        for(int i = 0 ; i < m ; i++)
            for(int j = 0 ; j <  n  ; j++)
            {
                scanf("%d",&mat[i][j]);
                suma_linie[i] += mat[i][j];
            }
    }
    for(int i = 0; i < m ; i++)
        suma_totala += suma_linie[i];
}

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

void suma()
{
    suma_curenta = suma_totala;
    for(int i = 0 ; i < r; i++)
    {
        int linie = combinari[i] - 1;
        suma_curenta -= suma_linie[linie];
        linie_taiata[linie] = true;
    }
    for(int j = 0 ; j < n ; j++)
    {
        for(int i = 0 ; i < m ; i++)
            if(linie_taiata[i] == false)
               suma_coloana[j] += mat[i][j];
    }
    sort(suma_coloana,suma_coloana + n);
    for(int i = 0 ; i < c ; 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();
       if(suma_curenta > suma_maxima)
        suma_maxima = suma_curenta;
       printf("%d",suma_maxima);
}

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