TPC追いコン B - ライツアウト ( Binary Enumeration )

B: ライツアウト - TPC追いコン | AtCoder
定数倍で TLEしまくって諦めた。どうして時間がこんなにきついんだろう。。
1753 -- Flip Game
同じような問題だけど、今度のは bitによる状態の変化を加速するための前処理でやらないと通らない。以下のはギリギリで通らないバージョン。

// Will TLE for large test cases, for some constant factor
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXWH = 400 + 2;
const int MAXH = 400 + 2;
const int MAXW = 400 + 2;
const int MAXN = MAXWH;
#define rep( i, a ) for(int i = 0; i < (int)( a ); ++i)

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

int h, w;
int n;

typedef vector<int> vec;
typedef vector<vec> mat;

int cur[ MAXH ][ MAXW ];

bool outOfRange(int x, int y){
    return x < 0 || x >= h || y < 0 || y >= w;
}

void flip(int x, int y){
    ++cur[ x ][ y ];
    rep( d, 4 ){
        int nx = x + dx[ d ];
        int ny = y + dy[ d ];
        if( outOfRange( nx, ny ) ) continue;
        ++cur[ nx ][ ny ];
    }
}

void solve(const mat &s, const mat &b){
    int ans = INF;
    rep( S, ( 1 << w ) ){
        memset( cur, 0, sizeof(cur) );
        bool ok = true;
        int cnt = 0;
        rep( i, w ){
            if( ( S >> i ) & 1 ){
                ++cnt;
                if( b[ 0 ][ i ] ){
                    ok = false;
                    break;
                }
                flip( 0, i );
            }
        }
        if( !ok ) continue;
        rep( i, h ){
            if( i == 0 ) continue;
            rep( j, w ){
                if( ( cur[ i - 1 ][ j ] + s[ i - 1 ][ j ] ) & 1 ){
                    ++cnt;
                    if( b[ i ][ j ] ){
                        ok = false;
                        break;
                    }
                    flip( i, j );
                }
            }
            if( !ok ) break;
        }
        if( !ok ) continue;
        rep( i, w ) if( ( cur[ h - 1 ][ i ] + s[ h - 1 ][ i ] ) & 1 )
            ok = false;
        if( ok ) ans = min<int>( ans, cnt );
    }
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &h, &w);
    mat s( h, vec( w ) ), b( h, vec( w ) );
    rep( i, h ) rep( j, w )
        scanf("%d", &s[ i ][ j ]);
    scanf("%d", &n);
    rep( i, n ){
        int x, y; scanf("%d%d", &x, &y);
        b[ y ][ x ] = 1;
    }
    if( h < w ){
        mat rs( w, vec( h ) ), rb( w, vec( h ) );
        rep( i, h ) rep( j, w ){
            rs[ j ][ i ] = s[ i ][ j ];
            rb[ j ][ i ] = b[ i ][ j ];
        }
        swap( s, rs );
        swap( b, rb );
        swap( h, w );
    }
    solve( s, b );
    return 0;
}