scuba, C++ (gcc) - rextester

scuba

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000007
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define loop(i,a,n) for(int i=a;i<n;i++)
#define trav(a,x) for(auto &a:x)
#define vi vector<int>
#define vl vector<ll>
#define pii pair<ll,ll>
#define w 1e5
int  t,a,n;
int  ox[200],ni[200],v[2000];
int dp[2010][201][200];
void pre()
{
    loop(i,0,2010)
    {
        loop(j,0,201)
        {
            loop(k,0,200)
            dp[i][j][k]=-1;
        }
    }
}
int fun(int i,int p,int q)
{
    if(dp[i][p][q]!=-1)
    return dp[i][p][q];
    if(i==n)
    {
        if(p<=ox[i] && q<=ni[i] && p>0 && q>0 )
        return dp[i][p][q]=v[i];
        if(p==0 && q==0)
            return 0;
        else 
            return dp[i][p][q]=1e7;
    }
    if(ox[i]>p && ni[i]>q)
    return dp[i][p][q]=min(fun(i+1,p,q),v[i]+fun(i+1,0,0));
    if(ox[i]>p && ni[i]<q)
    return dp[i][p][q]=min(fun(i+1,p,q),fun(i+1,0,q-ni[i])+v[i]);
    if(ox[i]<p && ni[i]>q)
    return dp[i][p][q]=min(fun(i+1,p,q),v[i]+fun(i+1,p-ox[i],0));
    else
    return dp[i][p][q]=min(fun(i+1,p,q),v[i]+fun(i+1,p-ox[i],q-ni[i]));
    
}
void solve()
{
       cin>>t>>a>>n;
       pre();
       loop(i,1,n+1)
       cin>>ox[i]>>ni[i]>>v[i];
       int x=fun(1,t,a);
       cout<<x<<endl;
}
int main() {
	// your code goes here
	io;
	int t ;
	cin>>t;
	while(t--)
    solve();
	return 0;
}


run \| edit \| history \| help	0