提出 #68156235

---

ソースコード 拡げる

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops,fast-math")
//#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
int n,p[10010],a[10010],b[10010],q,t,dp[10010][1001],sm[10010];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i=1;i<=n;i++) {
        cin >> p[i] >> a[i] >> b[i];
        sm[i]=sm[i-1]+b[i];
    }
    for(int i=0;i<=1000;i++) dp[n+1][i]=i;
    for(int i=n;i;i--) {
        int kk=p[i], aa=a[i], bb=b[i];
        for(int j=0;j<=kk;j++) dp[i][j]=dp[i+1][j+aa];
        for(int j=kk+1;j<1001;j++) dp[i][j]=dp[i+1][max(0,j-bb)];
    }
    //for(int i=1;i<=n;i++) cout << sm[i] << " ";
    for(cin >> q;q--;) {
        cin >> t;
        if(t<1001) cout << dp[1][t] << "\n";
        else {
            int zz=lower_bound(&sm[0],&sm[n+1],t-1000)-&sm[0];
           // cout << zz << " ";
            if(zz==n+1) cout << t-sm[n] << "\n";
            else cout << dp[zz+1][t-sm[zz]] << "\n";
        }
    }
}

提出情報

ジャッジ結果