Cod sursa(job #3200846)

Utilizator IoanMasterUngureanu Ioan IoanMaster Data 5 februarie 2024 20:52:28
Problema Jocul Flip Scor 80
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <set>
#include <cstring>

using namespace std;

ifstream fin("flip.in");
ofstream fout("flip.out");

int n, m, v[101], f[101], a[101][101], smax;
void flip(int k)
{
    int i, j, stotal = 0;

    for (i = 1; i <= k; i++)
    {
        for (j = 1; j <= n; j++)
            a[v[i]][j] *= (-1);
    }

    for (j = 1; j <= m; j++)
    {
        int s = 0;
        for (i = 1; i <= n; i++)
            s += a[i][j];

        if (s < 0)
            s *= (-1);

        stotal += s;
    }

    smax = max(smax, stotal);

    for (i = 1; i <= k; i++)
    {
        for (j = 1; j <= n; j++)
            a[v[i]][j] *= (-1);
    }
}

bool valid(int k)
{
    int i;

    for (i = 1; i < k; i++)
        if (v[i] == v[k])
            return false;

    if (k > 1 && v[k] <= v[k - 1])
        return false;

    return true;
}

void bkt(int k)
{
    int i;

    for (i = 1; i <= n; i++)
    {
        v[k] = i;

        if (valid(k))
        {
            flip(k);

            bkt(k + 1);
        }
    }
}

int main()
{
    fin >> n >> m;
    int i, j;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            fin >> a[i][j];

    bkt(1);

    fout << smax;

    return 0;
}