結果

問題 No.1598 4×4 Grid
コンテスト
ユーザー qqq xxa
提出日時 2021-07-22 21:02:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 428 ms / 4,000 ms
コード長 1,334 bytes
コンパイル時間 1,820 ms
コンパイル使用メモリ 170,968 KB
実行使用メモリ 210,688 KB
最終ジャッジ日時 2024-07-17 15:15:50
合計ジャッジ時間 7,273 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll solve() {
    ll K;
    cin >> K;

    int msk1 = 0x7777, msk2 = 0xEEEE, msk3 = 0xFFF, msk4 = 0xFFF0;
    ll M = 1<<16, A = 400;
    vector<vector<ll>> dp(M,vector<ll>(A));
    dp[0][0] = 1;
    for ( int b = 0; b < M; b++ ) {
        int mb = b ^ 0xFFFF;
        int n = __builtin_popcount(mb);
        int bs = mb;
        int bc = 0;
        for ( int bs = mb; bs > 0; bs ^= bc ) {
            bc = bs & -bs;  // lowest bit
            ll c = 0;
            if ( (bc&msk1)!=0 ) {
                if ( ((bc<<1)&b)==0 ) c += n;
                else c -= n;
            }
            if ( (bc&msk2)!=0 ) {
                if ( ((bc>>1)&b)==0 ) c += n;
                else c -= n;
            }
            if ( (bc&msk3)!=0 ) {
                if ( ((bc<<4)&b)==0 ) c += n;
                else c -= n;
            }
            if ( (bc&msk4)!=0 ) {
                if ( ((bc>>4)&b)==0 ) c += n;
                else c -= n;
            }
            for ( int j = 0; j < A; j++ ) {
                if ( j+c < 0 || j+c >= A) continue;
                dp[b|bc][j+c] += dp[b][j];
            }
        }
    }

    ll ans = dp[M-1][K];
    if ( ans == -1 ) ans = 0;
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}
0