Cod sursa(job #2450057)

Utilizator CharacterMeCharacter Me CharacterMe Data 21 august 2019 18:13:16
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
///N=16
///M=16
using namespace std;
///
int n, m, i, j, k, sum, out;
int flip[17][17], lines[17], sumc[17];
///
void read();
void solve();
void write();
void bkt(int i);
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("flip.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; ++i) for(j=1; j<=m; ++j) {scanf("%d", &flip[i][j]); sum+=flip[i][j];}
    fclose(stdin);
}
void solve(){
    if(n>m){
        for(i=1; i<=n; ++i) for(j=1; j<i; ++j) swap(flip[i][j], flip[j][i]);
        swap(n, m);
    }
    for(i=1; i<=n; ++i) for(j=1; j<=m; ++j) sumc[j]+=flip[i][j];
    bkt(0);
}
void write(){
    freopen("flip.out", "w", stdout);
    printf("%d ", out);
    fclose(stdout);
}
void bkt(int i){
    int s=0;
    for(int j=1; j<=m; ++j) if(sumc[j]<0) s-=sumc[j]; else s+=sumc[j];
    out=max(out, s);
    for(int j=lines[i]+1; j<=n; ++j){
        for(int k=1; k<=m; ++k) {
            sumc[k]-=2*flip[j][k];
            sum-=2*flip[j][k];
            flip[j][k]=-flip[j][k];
        }
        lines[i+1]=j;
        bkt(i+1);
        for(int k=1; k<=m; ++k){
            sumc[k]-=2*flip[j][k];
            sum-=2*flip[j][k];
            flip[j][k]=-flip[j][k];
        }
    }
}