Cod sursa(job #2463466)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 28 septembrie 2019 11:55:02
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
#define MAX_SIZE 17
int n, m, i, j, k, nextline, nextcolumn, index, done;
int table[MAX_SIZE][MAX_SIZE];
int sumlin[MAX_SIZE];
int sumcol[MAX_SIZE];
long int summin, suma, prevsum = -1000000000, sum = -999999999, summax = -1000000000;
bool minIsLine;

int SearchLinesAndColumns() {
    summin = sumlin[1];
    for(i = 2; i <= n; i++) {
        if(sumlin[i] < summin) {
            summin = sumlin[i];
            index = i;
            minIsLine = true;
        }
    }
    for(j = 1; j <= m; j++) {
        if(sumcol[j] < summin) {
            summin = sumcol[j];
            index = j;
            minIsLine = false;
        }
    }

    if(summin < 0)
        return index;
    return -1;
}

void ChangeLine(int nextline) {
    sumlin[nextline] = -sumlin[nextline];
    for(j = 1; j <= m; j++) {
        table[nextline][j] = -table[nextline][j];
        sumcol[j] += 2*table[nextline][j];
    }
}

void ChangeColumn(int nextcolumn) {
    sumcol[nextcolumn] = -sumcol[nextcolumn];
    for(i = 1; i <= n; i++) {
        table[i][nextcolumn] = -table[i][nextcolumn];
        sumlin[i] += 2*table[i][nextcolumn];
    }
}

int main()
{
    f >> n >> m;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            f >> table[i][j];
            sumlin[i] += table[i][j];
            sumcol[j] += table[i][j];
        }
    }

    while(prevsum <= sum && index != -1) {
        index = SearchLinesAndColumns();
        if(index != -1) {
            if(minIsLine)
                ChangeLine(index);
            else ChangeColumn(index);

            prevsum = sum;
            sum = 0;
            for(i = 1; i <= n; i++)
                sum += sumlin[i];
            if(sum > summax)
                summax = sum;
        }
    }

    g << summax;
    return 0;
}