Cod sursa(job #2313126)

Utilizator cameliapatileaPatilea Catalina Camelia cameliapatilea Data 6 ianuarie 2019 02:15:14
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int matrice[20][10005],suma,aux, n, m,c, r, rezultat = -99999999, nr[100005], v[20];
void suma_elementelor()
{
    nr[0] = 0;
    //calculez suma pe fiecare coloana in parte
    for(int j = 1; j <= n; j++)
    {
        suma = 0;
        for(int i = 1; i <= m; i++)
            if(v[i] == 0)
                suma = suma + matrice[i][j];
        // nr[0]++;
        //pastrez intr-un vector suma pe fiecare coloana
        nr[++nr[0]] = suma;
    }
    //sortez vectorul incepand cu prima pozitie pana la nr total de sume
    sort(nr + 1, nr + 1 +nr[0]);
    suma  =0;
    //fac suma sumelor ramaseincepand de la nr coloanei c pana la nr de sume
    for(int i = c +1; i <= nr[0]; i++)
        suma = suma + nr[i];
    if(rezultat < suma)
        rezultat = suma;
}
void backtracking(int x, int y)
{

    for(int i = 0; i < 2; i++)
    {
        v[x] = i;
        //daca am ajuns in varful stivei, nu mai pot adauga
        if(x == m)
        {
            if(y + v[x] == r)
                suma_elementelor();
        }
        else backtracking(x + 1, y + v[x]);

    }
}
int main()
{

    FILE *f = fopen("elimin.in", "r+");
    FILE *g = fopen("elimin.out", "w+");

    fscanf(f, "%d%d%d%d", &m, &n, &r, &c);
    if(m > n)
    {for(int i = 1; i<= m; i++)
            for(int j = 1; j <= n; j++)
                //citesc matricea invers, incepand cu ultima coloana
                fscanf(f, "%d", &matrice[j][m - i + 1]);
        aux = m;
        m = n;
        n = aux;
        aux = r;
        r = c;
        c = aux;

    }
    else{
        for(int i = 1; i<= m; i++)
            for(int j = 1; j<= n; j++)
                fscanf(f, "%d", &matrice[i][j]);
    }
    backtracking(1, 0);
    fprintf(g, "%d ", rezultat);
    return 0;

}