結果

問題 No.3509 Get More Money
コンテスト
ユーザー Naru820
提出日時 2026-03-02 23:41:09
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,631 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,187 ms
コンパイル使用メモリ 341,400 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-17 19:31:04
合計ジャッジ時間 13,640 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

struct SlopeTrick {
    const ll INF = 1e18; 
    ll min_f;
    ll add_l, add_r;
    map<ll, ll> L, R; 
    ll total_count_R; 
    SlopeTrick() : min_f(0), add_l(0), add_r(0), total_count_R(0) {}
    void add_x_minus_a(const ll& a, ll count) {
        if (count == 0) return;
        L[a - add_l] += count;
        
        ll rem = count;
        while (rem > 0 && !L.empty()) {
            auto it = L.rbegin();
            ll l_val = it->first + add_l;
            ll exist = it->second;
            ll move = min(rem, exist);
            
            if (l_val > a) {
                min_f += move * (l_val - a);
            }
            
            if (move == exist) L.erase(next(it).base());
            else it->second -= move;
            
            R[l_val - add_r] += move;
            total_count_R += move;
            
            rem -= move;
        }
    }

    void add_a_minus_x(const ll& a, ll count) {
        if (count == 0) return;
        
        R[a - add_r] += count;
        total_count_R += count;
        
        ll rem = count;
        while (rem > 0 && !R.empty()) {
            auto it = R.begin();
            ll r_val = it->first + add_r;
            ll exist = it->second;
            ll move = min(rem, exist);
            
            if (a > r_val) {
                min_f += move * (a - r_val);
            }
            
            if (move == exist) R.erase(it);
            else it->second -= move;
            total_count_R -= move;
            
            L[r_val - add_l] += move;
            
            rem -= move;
        }
    }
    void clear_left() {
        L.clear();
        add_l = 0;
    }
    
    void limit_slope_max(ll K) {
        while (total_count_R > K) {
            auto it = R.rbegin();
            ll exist = it->second;
            ll remove_count = min(exist, total_count_R - K);
            if (remove_count == exist) {
                R.erase(next(it).base());
            } else {
                it->second -= remove_count;
            }
            total_count_R -= remove_count;
        }
    }
};

int main() {
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n),b(n),c(n),d(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];
    for(int i = 0; i < n; i++) cin >> d[i];
    SlopeTrick st;
    for (int i = 0; i < n; ++i) {
        st.add_x_minus_a(a[i], b[i]);
        st.add_a_minus_x(c[i], d[i]);
        st.clear_left();
        st.limit_slope_max(k);
    }
    cout << st.min_f << endl;
}
0