WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #191 Div2 A "Flipping Game"

問題

http://codeforces.com/contest/327/problem/A

ラハブは退屈しのぎに紙を使って遊ぶゲームを考えた。

彼はa1, a2, ..., anのn個の整数を書いた。各整数は0か1のどちらかである。彼は1回だけ次のような操作を行う。彼は2つのインデックスiとj(1 <= i <= j <= n)を選び、インデックス[i, j]の範囲の、全ての整数をフリップする。値xをフリップするとは、x = 1 - xとすることを意味する。

上記の操作を行った後の、1の数を最大化せよ。

制約

1 <= n <= 100



チュートリアルを見て

O(n)でやる方法がわからん・・・
しょうがない、O(n^3)でやろう



ソースコード

int main() {
    int N;
    int a[110];
    cin >> N;

    for( int i = 0; i < N; i++ ){
        cin >> a[i];
    }

    int ans = 0;
    for( int l = 0; l < N; l++ ){
        for( int r = l; r < N; r++ ){
            int b[110];
            memcpy( b, a, sizeof(a) );
            for( int i = l; i <= r; i++ ){
                b[i] = 1 - b[i];
            }
            int res = 0;
            for( int i = 0; i < N; i++ ){
                res += b[i];
            }
            ans = max( ans, res );
        }
    }

    cout << ans << endl;
}