Cod sursa(job #1072634)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 4 ianuarie 2014 18:05:31
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>
 
 
const static int NMAX = 700;
 
using namespace std;
 
int nr_linii , nr_coloane , matrix[NMAX][NMAX];
int R , C;
 
int solutie[NMAX];
 
int sum_linii[NMAX] , aux_sum_linii[NMAX];
int sum_matrix = 0;
int max_suma = -1;
 
ifstream input("elimin.in");
ofstream output("elimin.out");
 
 
void backtrack(int pos)
{
    if (pos > C)
    {
        int sum = 0;
         
 
        for (int i = 0;i<nr_linii;i++)
        {
            aux_sum_linii[i] = 0;
            for (int j = 1;j<pos;j++)
            {
                sum += matrix[i][solutie[j]];
                aux_sum_linii[i] += matrix[i][solutie[j]];
            }
            aux_sum_linii[i] = sum_linii[i] - aux_sum_linii[i];
        }
 
        sort(aux_sum_linii , aux_sum_linii + nr_linii);
 
        for (int i = 0;i<R;i++)
            sum += aux_sum_linii[i];
 
        if (sum_matrix - sum > max_suma)
            max_suma = sum_matrix - sum;        
 
    }
    else
    {
        for (int i = solutie[pos-1] + 1;i<nr_coloane;i++)
        {
            solutie[pos] = i;
            backtrack(pos+1);
        }
    }
}
 
 
 
int main(int argc , char ** argv)
{
    input >> nr_linii >> nr_coloane >> R >> C;
 
    if (nr_linii > nr_coloane)
    {
 
        for (int i = 0;i<nr_linii;i++)
            for (int j = 0;j<nr_coloane;j++)
                input >> matrix[i][j];
    }
    else
    {
        for (int i = 0;i<nr_linii;i++)
            for (int j = 0;j<nr_coloane;j++)
                input >> matrix[j][i];
 
        swap(nr_linii , nr_coloane);
        swap(R , C);
    }
 
 
    int sum = 0;
    for (int i = 0;i<nr_linii;i++)
    {
        sum = 0;
        for (int j = 0;j<nr_coloane;j++)
        {
            sum_matrix += matrix[i][j];
            sum += matrix[i][j];
        }
        sum_linii[i] += sum;
    }
 
 
    solutie[0] = -1;
 
    backtrack(1);
 
    output << max_suma;
 
    input.close();
    output.close();
 
    return 0;
}