19B - Checkout Assistant - CodeForces Solution

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

// Shorthands
#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define endl "\n"

#define int long long
#define ll long long
#define ld long double
#define vll vector<ll>
#define vvll vector<vll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll, ll>
#define vpll vector<pll>
#define ff first
#define ss second
#define fill(a, b) memset(a, b, sizeof(a))
#define tll tuple<ll, ll, ll>
#define vtll vector<tll>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define vect(a, n) \
    vll a(n);      \
    rep(i, 0, n) cin >> a[i];
#define all(a) a.begin(), a.end()
#define sortall(a) sort(a.begin(), a.end());
#define PI acos(-1)
#define print cout <<
const int mod = 1000000007;
int helper(int i,int j,vector<vector<int>> &v,vector<vector<int>> &dp){
    if(j>=4000)return 0;
    if(i>=v.size()){
        if(j>=2000)return 0;
        return 1e18;
    }
    if(dp[i][j]!=-1)return dp[i][j];
    int sel=0;int notsel=0;
    sel=v[i][1]+helper(i+1,j+v[i][0],v,dp);
    notsel=helper(i+1,j-1,v,dp);
    return dp[i][j]=min(sel,notsel);
}
void solve()
{
    int a;cin>>a;
    vector<vector<int>> v;
    for(int i=0;i<a;i++){
        int p,q;cin>>p>>q;
        v.pb({p,q});
    }
    vector<vector<int>> dp(2001,vector<int> (4002,-1)); 
    int ans=helper(0,2000,v,dp);
    cout<<ans<<endl;
}
signed main()
{

    int t;
    t = 1;
    // cin >> t;
    
    while (t--)
    {
        solve();
    }
}