Cod sursa(job #2027131)

Utilizator shantih1Alex S Hill shantih1 Data 25 septembrie 2017 17:51:13
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("elimin.in");
ofstream fout("elimin.out");

int i, j, n, m, r, c, k, rez, sum, nr, ss[750], s, sl[750];
int x[750], v[750][750];

int suma() {
    
    int mins = 0;
    for (int i = 1; i <= k; i++)
    {
        v[x[i]][0] = 1;
        mins += sl[x[i]];
    }
    
    int s = 0;
    for (j = 1; j <= m; j++)
    {
        s = 0;
        for (i = 1; i <= n; i++)
            if (v[i][0] == 0)
                s += v[i][j];
        
        ss[j] = s;
    }
    
    sort(ss+1, ss+m+1);
    
    for (i = 1; i <= c; i++)
        mins += ss[i];
    
    for (i = 1; i <= n; i++)
        v[i][0] = 0;
    
    nr++;
    return sum - mins;
}

void back(int p) {
    
    int c;
    for (int i = x[p-1] + 1; i <= n; i++)
    {
        x[p] = i;
        if (p == k)
        {
            c = suma();
            if (c > rez)    rez = c;
        }
        else back(p + 1);
    }
}

int main () {
    
    fin >> n >> m >> r >> c;
    
    if (n > m)
    {
        i = n;  n = m;  m = i;
        i = r;  r = c;  c = i;
        for (j = 1; j <= m; j++)
            for (i = n; i >= 1; i--)
            {
                fin >> v[i][j];
                sum += v[i][j];
                sl[i] += v[i][j];
            }
    }
    else
        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
            {
                fin >> v[i][j];
                sum += v[i][j];
                sl[i] += v[i][j];
            }
    
    k = r;
    back(1);
    
    if (r == 0)
        rez = suma();
    fout << rez << "\n";
    return 0;
}