結果

問題 No.3322 引っ張りだこ
コンテスト
ユーザー GOTKAKO
提出日時 2025-11-01 00:05:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,844 bytes
コンパイル時間 2,521 ms
コンパイル使用メモリ 219,844 KB
実行使用メモリ 24,712 KB
最終ジャッジ日時 2025-11-01 00:05:32
合計ジャッジ時間 10,743 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while(T--){
        int N,K; cin >> N >> K;
        vector<long long> A(N),B(N);
        for(auto &a : A) cin >> a;
        for(auto &b : B) cin >> b;

        if(K == 0){
            cout << accumulate(A.begin(),A.end(),0LL) << "\n";
            continue;
        }

        long long answer = 0;
        vector<long long> D(N);
        vector<int> plus,minus;
        bool isA = true;
        int move = 0;
        for(int i=0; i<N; i++){
            answer += min(A.at(i),B.at(i));
            D.at(i) = A.at(i)-B.at(i);
            if(D.at(i) >= 0) plus.push_back(i),move += !isA,isA = true;
            else minus.push_back(i),move += isA,isA = false;
        }
        if(isA) minus.push_back(N);
        else plus.push_back(N);

        vector<pair<long long,int>> diff;
        for(int i=0; i+1<plus.size(); i++){
            int p1 = plus.at(i),p2 = plus.at(i+1);
            if(p1+1 == p2) continue;
            long long dec = 0;
            for(int p=p1+1; p<p2; p++) dec += B.at(p)-A.at(p); 
            diff.push_back({dec,i+1});
        }
        for(int i=0; i+1<minus.size(); i++){
            int p1 = minus.at(i),p2 = minus.at(i+1);
            if(p1+1 == p2) continue;
            long long dec = 0;
            for(int p=p1+1; p<p2; p++) dec += A.at(p)-B.at(p); 
            diff.push_back({dec,-(i+1)});
        }
        sort(diff.rbegin(),diff.rend());
    

        auto memodiff = diff;
        int memomove = move;
        set<int> S;
        for(int i=0; i<N; i++) S.insert(i);
        while(move > K){
            auto [ign,pos] = diff.back(); diff.pop_back();
            int p1,p2;
            if(pos > 0) p1 = plus.at(pos-1),p2 = plus.at(pos);
            else p1 = minus.at(-pos-1),p2 = minus.at(-pos);
            if(!S.count(abs(p1))) continue;
            move -= 2;
            if(p2 == N) move++;
            for(int p=p1+1; p<p2; p++) S.erase(p);
        }
        long long answer2 = answer;
        for(auto pos : S) answer += max(A.at(pos),B.at(pos))-min(A.at(pos),B.at(pos));
        swap(answer,answer2);
        diff = memodiff,move = memomove;
        for(int i=0; i<N; i++) S.insert(i);
        while(move > K && diff.size()){
            auto [ign,pos] = diff.back(); diff.pop_back();
            int p1,p2;
            if(pos > 0) p1 = plus.at(pos-1),p2 = plus.at(pos);
            else p1 = minus.at(-pos-1),p2 = minus.at(-pos);
            if(p2 == N) continue;
            if(!S.count(abs(p1))) continue;
            move -= 2;
            for(int p=p1+1; p<p2; p++) S.erase(p);
        }
        if(move <= K) for(auto pos : S) answer += max(A.at(pos),B.at(pos))-min(A.at(pos),B.at(pos));
        cout << max(answer,answer2) << "\n";
    }
}
0