Submission #68125775

---

Source Code Expand

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn = 10000+5;
int a[maxn],b[maxn],p[maxn];
int sum[maxn];
int dp[maxn][1005];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>p[i]>>a[i]>>b[i];
        sum[i]=sum[i-1]+b[i];
    }
    for (int j=0;j<=1001;j++)
        dp[n+1][j]=j;
    for (int i=n;i>0;i--)
    {
        for (int j=0;j<=1001;j++)
        {
            if (p[i]>=j)
                dp[i][j]=dp[i+1][min(1001,j+a[i])];
            else
                dp[i][j]=dp[i+1][max(0,j-b[i])];
        }
    }
    int q;
    cin>>q;
    while (q--)
    {
        int x,d=1;
        cin>>x;
        if (x>500)
        {
            d=lower_bound(sum+1,sum+n+1,x-500)-sum;
            if (d>n)
            {
                x-=sum[n];
                cout<<x<<'\n';
                continue;
            }
            x-=sum[d];
            d++;
        }
        if (d==n+1)
            cout<<x<<'\n';
        else
            cout<<dp[d][x]<<'\n';
    }
}

Submission Info

Judge Result