結果

問題 No.3041 非対称じゃんけん
コンテスト
ユーザー bal4u
提出日時 2025-03-04 19:13:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,052 bytes
コンパイル時間 2,430 ms
コンパイル使用メモリ 197,596 KB
実行使用メモリ 12,448 KB
最終ジャッジ日時 2025-03-04 19:13:38
合計ジャッジ時間 8,848 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

vector<uint64_t> shiftVec(const vector<uint64_t>& v, int s, int L) {
    int nblock = v.size();
    vector<uint64_t> res(nblock, 0);
    int bs = s / 64;
    int r = s % 64;
    for (int i = nblock - 1; i >= 0; i--) {
        int j = i - bs;
        if(j < 0) continue;
        uint64_t cur = v[j] << r;
        uint64_t carry = 0;
        if(r && j > 0) carry = v[j-1] >> (64 - r);
        uint64_t val = cur | carry;
        res[i] |= val;
    }
    int full = L / 64;
    int rem = L % 64;
    if(full < nblock && rem != 0){
        res[full] &= ((uint64_t)1 << rem) - 1;
        for (int i = full+1; i < nblock; i++) res[i] = 0;
    }
    return res;
}

void orVec(vector<uint64_t>& d, const vector<uint64_t>& s) {
    int n = d.size();
    for (int i = 0; i < n; i++) d[i] |= s[i];
}

int countVec(const vector<uint64_t>& v, int L) {
    int nblock = v.size();
    int full = L / 64;
    int rem = L % 64;
    int cnt = 0;
    for (int i = 0; i < full; i++) cnt += __builtin_popcountll(v[i]);
    if(full < nblock && rem != 0){
        uint64_t mask = ((uint64_t)1 << rem) - 1;
        cnt += __builtin_popcountll(v[full] & mask);
    }
    return cnt;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, F;
    cin >> N >> F;
    vector<int> A(N), B(N), C(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];
    for (int i = 0; i < N; i++) cin >> C[i];

    int max_sum = N * F;
    int L = max_sum + 1;
    int nblock = (L + 63) / 64;

    vector<uint64_t> dp(nblock, 0);
    dp[0] = 1;

    int cur = 0;

    for (int i = 0; i < N; i++){
        cur += F;
        int Lnow = cur + 1;
        vector<uint64_t> ndp(nblock, 0);
        vector<uint64_t> t;

        t = shiftVec(dp, A[i], Lnow);
        orVec(ndp, t);
        t = shiftVec(dp, B[i], Lnow);
        orVec(ndp, t);
        t = shiftVec(dp, C[i], Lnow);
        orVec(ndp, t);
        dp.swap(ndp);
        cout << countVec(dp, Lnow) << endl;
    }
    return 0;
}
0