結果

問題 No.3407 Birds-of-Paradise' Christmas Live
コンテスト
ユーザー hirayuu_yc
提出日時 2025-12-12 22:55:21
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 5,347 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,843 ms
コンパイル使用メモリ 286,124 KB
実行使用メモリ 16,896 KB
最終ジャッジ日時 2025-12-13 23:30:11
合計ジャッジ時間 4,753 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 NEG = LLONG_MIN / 4;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin >> n)) return 0;
    vector<int64> w(n);
    for(int i=0;i<n;i++) cin >> w[i];
    int m; cin >> m;
    vector<int64> s(m);
    for(int i=0;i<m;i++) cin >> s[i];

    // ポインタで走長列をマージして、(bitW, bitS, len) のセグメント列を作る
    int iw = 0, is = 0;
    int64 remW = (n>0? w[0] : 0);
    int64 remS = (m>0? s[0] : 0);
    vector<tuple<int,int,int64>> segs; // (bitW, bitS, len)
    while(iw < n && is < m){
        int bitW = (iw % 2 == 0) ? 1 : 0; // w1 is ones => iw=0 => 1
        int bitS = (is % 2 == 0) ? 1 : 0; // same for s
        int64 take = min(remW, remS);
        segs.emplace_back(bitW, bitS, take);
        remW -= take;
        remS -= take;
        if(remW == 0){
            iw++;
            if(iw < n) remW = w[iw];
        }
        if(remS == 0){
            is++;
            if(is < m) remS = s[is];
        }
    }

    // DP をセグメント列上で実行
    int64 answer = 0;

    // dpK_total: 総スコア（現在の進行中ランも既にスコアに含めた形）
    // dpK_len: 進行中の K ラン長（dpK_total に含まれているランの長さ）
    int64 dpK_total = NEG, dpK_len = 0;
    int64 dpT_total = NEG, dpT_len = 0;

    auto flush_block = [&](){
        if(dpK_total == NEG && dpT_total == NEG) return;
        int64 best = max(dpK_total, dpT_total);
        if(best != NEG) answer += best;
        dpK_total = dpT_total = NEG;
        dpK_len = dpT_len = 0;
    };

    for(auto &tp : segs){
        int bitW, bitS; int64 len;
        tie(bitW, bitS, len) = tp;
        if(bitW==0 && bitS==0){
            // separator: ブロック終了
            flush_block();
            continue;
        }
        // 保存しておく（遷移で上書きするので previous をキャプチャ）
        int64 prevK_total = dpK_total, prevK_len = dpK_len;
        int64 prevT_total = dpT_total, prevT_len = dpT_len;

        if(bitW==1 && bitS==0){
            // forced K
            // new dpK = max( extend prevK, start new from prevT )
            int64 cand1 = NEG, cand2 = NEG;
            if(prevK_total != NEG){
                // extend K
                cand1 = prevK_total + (2*prevK_len*len + len*len);
            }
            if(prevT_total != NEG){
                // switch from T to K, start new K run of length len
                cand2 = prevT_total + (len*len);
            }
            if(prevK_total == NEG && prevT_total == NEG){
                // beginning of block: start K here
                cand2 = len*len;
            }
            dpK_total = max(cand1, cand2);
            if(dpK_total == cand1) dpK_len = prevK_len + len;
            else dpK_len = len;
            // dpT impossible
            dpT_total = NEG; dpT_len = 0;
        } else if(bitW==0 && bitS==1){
            // forced T
            int64 cand1 = NEG, cand2 = NEG;
            if(prevT_total != NEG){
                cand1 = prevT_total + (2*prevT_len*len + len*len);
            }
            if(prevK_total != NEG){
                cand2 = prevK_total + (len*len);
            }
            if(prevK_total == NEG && prevT_total == NEG){
                cand2 = len*len;
            }
            dpT_total = max(cand1, cand2);
            if(dpT_total == cand1) dpT_len = prevT_len + len;
            else dpT_len = len;
            dpK_total = NEG; dpK_len = 0;
        } else {
            // bitW==1 && bitS==1 : flexible -> can be assigned to K or T
            // compute new dpK and dpT from previous both possibilities
            int64 newK_total = NEG, newK_len = 0;
            int64 newT_total = NEG, newT_len = 0;

            // to K:
            // extend prevK
            if(prevK_total != NEG){
                int64 val = prevK_total + (2*prevK_len*len + len*len);
                if(val > newK_total){ newK_total = val; newK_len = prevK_len + len; }
            }
            // start K from prevT or from nothing
            if(prevT_total != NEG){
                int64 val = prevT_total + (len*len);
                if(val > newK_total){ newK_total = val; newK_len = len; }
            }
            if(prevK_total == NEG && prevT_total == NEG){
                // starting block
                int64 val = len*len;
                if(val > newK_total){ newK_total = val; newK_len = len; }
            }

            // to T:
            if(prevT_total != NEG){
                int64 val = prevT_total + (2*prevT_len*len + len*len);
                if(val > newT_total){ newT_total = val; newT_len = prevT_len + len; }
            }
            if(prevK_total != NEG){
                int64 val = prevK_total + (len*len);
                if(val > newT_total){ newT_total = val; newT_len = len; }
            }
            if(prevK_total == NEG && prevT_total == NEG){
                int64 val = len*len;
                if(val > newT_total){ newT_total = val; newT_len = len; }
            }

            dpK_total = newK_total; dpK_len = newK_len;
            dpT_total = newT_total; dpT_len = newT_len;
        }
    }

    // 最後のブロックを足す
    flush_block();

    cout << answer << "\n";
    return 0;
}
0