Cod sursa(job #2854201)

Utilizator ValentValentin Lavric Valent Data 21 februarie 2022 00:34:16
Problema Jocul Flip Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <set>
using namespace std;

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

int n, m, a[20][20], max_sum;
set<int, greater<int>> lin, col;

void flip(int k)
{
    for (int i = 1; i <= m; ++i)
        a[k][i] *= -1;
}

void flip2(int k)
{
    for (int i = 1; i <= n; ++i)
        a[i][k] *= -1;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            fin >> a[i][j];
            a[0][j] += a[i][j];
            a[i][0] += a[i][j];
        }
    for (int i = 1; i <= n; ++i)
        if (a[i][0] < 0)
            lin.insert(i);
    for (int i = 1; i <= m; ++i)
        if (a[0][i] < 0)
            col.insert(i);
    while (!lin.empty() && !col.empty())
        if (a[*lin.begin()][0] < a[0][*col.begin()])
        {
            flip(*lin.begin());
            lin.erase(*lin.begin());
        }
        else
        {
            flip2(*col.begin());
            col.erase(*col.begin());
        }
    if (!lin.empty())
    {
        flip(*lin.begin());
        lin.erase(*lin.begin());
    }
    if (!col.empty())
    {
        flip2(*col.begin());
        col.erase(*col.begin());
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            max_sum += a[i][j];
    
    fout << max_sum;

    fin.close();
    fout.close();

    return 0;
}