結果

問題 No.3407 Birds-of-Paradise' Christmas Live
コンテスト
ユーザー GOTKAKO
提出日時 2025-12-14 00:14:05
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 1,816 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,164 ms
コンパイル使用メモリ 205,920 KB
実行使用メモリ 28,440 KB
最終ジャッジ日時 2025-12-14 00:14:10
合計ジャッジ時間 4,596 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

    int N; cin >> N;
    vector<long long> W(N);
    for(auto &w : W) cin >> w;
    int M; cin >> M;
    vector<long long> S(M);
    for(auto &s : S) cin >> s;
 
    vector<tuple<int,int,long long>> T;
    int pos1 = 0,pos2 = 0;
    while(pos1 < N){
        long long &w = W.at(pos1),&s = S.at(pos2);
        long long now = min(w,s);
        T.push_back({pos1%2==0,pos2%2==0,now});
        w -= now,s -= now;
        if(w == 0) pos1++;
        if(s == 0) pos2++;
    }

    int n = T.size();
    for(int i=1; i<n-1; i++){
        auto &[w1,s1,l1] = T.at(i-1);
        auto &[w2,s2,l2] = T.at(i);
        auto &[w3,s3,l3] = T.at(i+1);
        if(w1+w2+w3 == 3 && s1 == 0 && s2 == 1 && s3 == 0) s2 = 0;
        if(s1+s2+s3 == 3 && w1 == 0 && w2 == 1 && w3 == 0) w2 = 0;
    }
    {
        vector<tuple<int,int,long long>> T2;
        for(auto [w,s,l] : T){
            if(T2.size()){
                auto &[w2,s2,l2] = T2.back();
                if(w2 == w && s == s2) l2 += l;
                else T2.push_back({w,s,l});
            }
            else T2.push_back({w,s,l});

        }
        swap(T,T2);
    }
    n = T.size();
    vector<long long> dp(n+1);
    for(int i=0; i<n; i++){
        long long len = 0;
        dp.at(i+1) = max(dp.at(i+1),dp.at(i));
        for(int k=i; k<n; k++){
            auto [w,s,l] = T.at(k);
            if(w == 0) break;
            len += l;
            dp.at(k+1) = max(dp.at(k+1),dp.at(i)+len*len);
        }
        len = 0;
        for(int k=i; k<n; k++){
            auto [w,s,l] = T.at(k);
            if(s == 0) break;
            len += l;
            dp.at(k+1) = max(dp.at(k+1),dp.at(i)+len*len);
        }
    }
    cout << dp.at(n) << endl;
}
0