結果

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

ソースコード

diff #
raw source code 

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

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);

    auto bit_of_index = [](int idx)->int { return (idx % 2 == 0) ? 1 : 0; }; // 0-based index: 0 -> w1 -> ones

    int64 answer = 0;

    // 現在のブロックの DP。started=false の間はブロック未開始（直前に (0,0) があった状態）
    bool started = false;
    // dpK_score: 現在「末尾がK」であるときの最大スコア（ブロック内のみ含む）
    // dpK_len: 末尾の連続忘れ K の長さ（スコアには既に含まれている）
    int64 dpK_score = 0, dpK_len = 0;
    int64 dpT_score = 0, dpT_len = 0;

    auto flush_block = [&](){
        if(!started) return;
        answer += max(dpK_score, dpT_score);
        started = false;
        dpK_score = dpK_len = dpT_score = dpT_len = 0;
    };

    while(iw < n && is < m){
        int bitW = bit_of_index(iw);
        int bitS = bit_of_index(is);
        int64 take = min(remW, remS);
        remW -= take;
        remS -= take;
        if(remW == 0){
            iw++;
            if(iw < n) remW = w[iw];
        }
        if(remS == 0){
            is++;
            if(is < m) remS = s[is];
        }

        // このセグメント (bitW,bitS,take) を処理
        if(bitW == 0 && bitS == 0){
            // セパレータ：ブロック終了
            flush_block();
            continue;
        }

        // ブロック内セグメントとして扱う
        if(!started){
            // ブロック開始時の初期化
            started = true;
            if(bitW==1 && bitS==0){
                // forced K
                dpK_score = take * take;
                dpK_len = take;
                dpT_score = 0; dpT_len = 0; // impossible
                // but keep dpT_score small so max works
            } else if(bitW==0 && bitS==1){
                dpT_score = take * take;
                dpT_len = take;
                dpK_score = 0; dpK_len = 0;
            } else { // bitW==1 && bitS==1 -> flexible
                // at block start we can choose either K or T for this flexible seg.
                dpK_score = take * take; dpK_len = take;
                dpT_score = take * take; dpT_len = take;
            }
            continue;
        }

        // 一般遷移
        if(bitW==1 && bitS==0){
            // forced K: T は impossible after this seg (cannot assign this seg to T)
            // new K can be extending previous K or starting new from previous T
            int64 cand_extendK = dpK_score + (2*dpK_len*take + take*take); // extend K run
            int64 cand_fromT = dpT_score + (take*take); // switch from T -> start new K run
            // It's possible dpK_score was 0 (if never had K before) but that's fine.
            if(dpK_len==0 && dpK_score==0 && dpT_len==0 && dpT_score==0){
                // shouldn't happen because started==true
            }
            if(cand_extendK >= cand_fromT){
                dpK_score = cand_extendK;
                dpK_len = dpK_len + take;
            } else {
                dpK_score = cand_fromT;
                dpK_len = take;
            }
            // dpT becomes impossible for now
            dpT_score = 0; dpT_len = 0;
        } else if(bitW==0 && bitS==1){
            // forced T
            int64 cand_extendT = dpT_score + (2*dpT_len*take + take*take);
            int64 cand_fromK = dpK_score + (take*take);
            if(cand_extendT >= cand_fromK){
                dpT_score = cand_extendT;
                dpT_len = dpT_len + take;
            } else {
                dpT_score = cand_fromK;
                dpT_len = take;
            }
            dpK_score = 0; dpK_len = 0;
        } else {
            // flexible (1,1): we may assign whole segment to K or to T.
            // compute newK by either extending K or starting new from T; similarly for newT.
            int64 newK_score1 = dpK_score + (2*dpK_len*take + take*take); // extend K
            int64 newK_score2 = dpT_score + (take*take); // switch from T -> start K
            int64 newK_score = max(newK_score1, newK_score2);
            int64 newK_len = (newK_score1 >= newK_score2) ? (dpK_len + take) : take;

            int64 newT_score1 = dpT_score + (2*dpT_len*take + take*take); // extend T
            int64 newT_score2 = dpK_score + (take*take); // switch from K -> start T
            int64 newT_score = max(newT_score1, newT_score2);
            int64 newT_len = (newT_score1 >= newT_score2) ? (dpT_len + take) : take;

            dpK_score = newK_score; dpK_len = newK_len;
            dpT_score = newT_score; dpT_len = newT_len;
        }
    }

    // 最後のブロックを確定
    flush_block();

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