Submission #73486499

---

Source Code Expand

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

using ll = long long;
using ld = long double;

const ll INF = (ll)4e18;
const ll MOD = 998244353;

ll T = 1;

ll dx[4]  = {1, 0, -1, 0};
ll dy[4]  = {0, 1, 0, -1};
ll dxx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
ll dyy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

template<class T, class U> using P = pair<T, U>;
template<class T, class U> using u_map = unordered_map<T, U>;
using pll = pair<ll,ll>;
using vs = vector<string>;
using vc = vector<char>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

template<class T> using pq = priority_queue<T>;
template<class T> using rpq = priority_queue<T, vector<T>, greater<T>>;
template<class T>

struct SegTree {
    int n;
    vector<T> dat;
    T E;
    function<T(T,T)> op;
    SegTree(ll _n, T _E, function<T(T,T)> _op){
        E = _E; op = _op;
        n = 1;
        while(n < _n) n <<= 1;
        dat.assign(2*n, E);
    }
    void set(ll i, T x){
        i += n;
        dat[i] = x;
        while(i >>= 1)dat[i] = op(dat[i<<1], dat[i<<1|1]);
    }
    T query(ll l, ll r){
        T L = E, R = E;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1){
            if(l & 1) L = op(L, dat[l++]);
            if(r & 1) R = op(dat[--r], R);
        }
        return op(L, R);
    }
};
//これは区間最小値
/*SegTree<ll> seg( 
    n,
    INF,
    [](ll a, ll b){ return min(a, b); }
);*/

template<typename T>
istream &operator>>(istream &is, vector<T> &v){
    for (T & in : v) is >> in;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (int64_t i = 0; i < (int64_t)v.size(); i++) {
        os << v[i] << (i + 1 != (int64_t)v.size() ? " " : "");
    }
    return os;
}
template<class T>
istream& operator>>(istream& is, vector<vector<T>>& v){
    for(auto& row : v)for(auto& x : row)is >> x;
    return is;
}
template<class T>
ostream& operator<<(ostream& os, const vector<vector<T>>& v){
    for(auto& row : v){
        for(int i = 0; i < (int)row.size(); i++)os << row[i] << (i+1 == (int)row.size() ? "" : " ");
        os << '\n';
    }
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << " " << p.second;
    return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template<class T>
bool chmax(T& a, const T& b){
    if(a < b){ a = b; return true; }return false;
}
template<class T>
bool chmin(T& a, const T& b){
    if(a > b){ a = b; return true; }return false;
}
template<class T>
void uniq(vector<T>& a){
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
}
ll digit_sum(ll x){
    ll s = 0;
    while(x){s += x % 10; x /= 10;}
    return s;
}
bool mul(ll a,ll b){return a % b == 0;}

#define rt return
#define F first
#define S second
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pb push_back
#define pob pop_back
#define Min(x) *min_element(all(x))
#define Max(x) *max_element(all(x))
#define has(m, x) ((m).find(x) != (m).end())
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define rep1(a) for(ll _=0;_<ll(a);_++)
#define rep2(i,a) for(ll i=0;i<(ll)(a);i++)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c))
#define rrep(i,a,b) for(ll i=(ll)(a);i>=(ll)(b);i--)
#define overload_rep(a, b, c, d, e, ...) e
#define rep(...) overload_rep(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

void solve();

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while(T--) solve();
}

void solve()
{
    ll n,d; cin>>n>>d;
    queue<pll> qu;
    vl aa(n),bb(n);cin>>aa>>bb;
    rep(i,n){
        ll a=aa[i],b=bb[i];
        qu.push({a,i});
        while(1){
            if(!qu.size())break;
            if(qu.front().F<=b){b-=qu.front().F; qu.pop();}
            else {qu.front().F-=b; b=0;}
            if(b==0)break;
        }
        while(1){
            if(!qu.size())break;
            if(i-qu.front().S>=d)qu.pop();
            else break;
        }
    }
    ll ans=0;
    while(qu.size()){ans+=qu.front().F; qu.pop();}
    cout<<ans<<endl;
}

Submission Info

Judge Result