Cod sursa(job #2313313)

Utilizator anca.rada24@gmail.comanca08 [email protected] Data 6 ianuarie 2019 17:03:18
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
const int NMAX = 20  ;
int S[NMAX], sol[(int)1e6]  ;
int mat[NMAX][NMAX], new_mat[NMAX][NMAX] ;
int s  ;
long long ans ;
bool modific[NMAX] ;
int n, m ;
 
void do_sol() {
    register int i, j  ;
    for (i = 1 ; i <= m ; ++ i)
        if (modific[i])
            for (j = 1 ; j <= n ; ++ j)
                new_mat[j][i] = -mat[j][i] ;
        else
            for (j = 1 ; j <= n ; ++ j)
                new_mat[j][i] = mat[j][i] ;
    long long S(0) ;
    for (i = 1 ; i <= n ; ++ i) {
        int sum = 0 ;
        for (j = 1 ; j <= m ; ++ j)
            sum += new_mat[i][j] ;
        sum > 0 ? S += sum : S -= sum ; }
    ans = MAX(ans, S) ; }
 
void backt(int k) {
    if (k == m + 1) {
        do_sol() ;
        return ; }
    modific[k] = 0 ;
    backt(k + 1) ;
    modific[k] = 1 ;
    backt(k + 1) ; }
int main() {
    freopen("flip.in", "r", stdin)  ;
    freopen("flip.out", "w", stdout)  ;
    register int i, j ;
    scanf("%d %d", &n, &m) ;
    for (i = 1 ; i <= n ; ++ i) {
        for (j = 1 ; j <= m ; ++ j) {
            scanf("%d", &mat[i][j]) ;
            ans += mat[i][j] ; } }
    for (i = 1 ; i <= m ; ++ i) {
        s = 0 ;
        for (j = 1 ; j <= n ; ++ j)
            s += mat[j][i] ;
        S[i] = s ; }
    backt(1) ;
    printf("%d", ans) ;
    return 0 ; 
	}