MINVEST, C++ (gcc)

MINVEST

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>

using namespace std;

#define fr(i,m,n) for(i=m;i<n;i++)
#define ifr(i,m,n) for(i=m;i>n;i--)
#define ll long long
#define ull unsigned ll
#define sc scanf
#define pf printf
#define var(x) x i=0,j=0,tmp1=0,tmp2=0,tmp3=0,tmp=0,tmp4=0,tmp5=0,flag=0,T=0,N=0,M=0,X,Y
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvii vector<vector<pair<int,int> > >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define all(c) c.begin(), c.end() 
#define br cout<<"\n"
#define sz 502
#define INTI_MAX 1000000000

vii bonds;
     
int knapSack(int W, int n)
{
   int i, w;
   int K[n+1][W+1];
 
   // Build table K[][] in bottom up manner
   for (int i = 0; i <= n; i++)
   {
       for (int w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (bonds[i-1].first <= w)
                 K[i][w] = max(bonds[i-1].second + K[i-1][w-bonds[i-1].first],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}

int knapSackRecur(int W, int n)
{
   // Base Case
   if (n == 0 || W == 0)
       return 0;
 
   // If weight of the nth item is more than Knapsack capacity W, then
   // this item cannot be included in the optimal solution
   if (bonds[n-1].first > W)
       return knapSack(W, n-1);
 
   // Return the maximum of two cases: (1) nth item included (2) not included
   else return max( bonds[n-1].second + knapSack(W-bonds[n-1].first, n-1),
                    knapSack(W, n-1));
}

int main()
{
    var(int);
    cin>>T;
    int prpl,years,d;
    
    while(T--)
    {
        bonds.clear();
        cin>>prpl>>years;
        cin>>d;
        fr(i,0,d)
        {
            cin>>tmp1>>tmp2;
            fr(j,0,(prpl/tmp1)+1)
                bonds.pb(make_pair(tmp1,tmp2));
        }
        
        cout<<bonds.size()<<"\n";

int interest;
        fr(i,0,years)
        {
            interest = knapSackRecur(prpl,bonds.size());
            prpl+=interest;
        }
        cout<<prpl<<"\n";
        
    }
}


run \| edit \| history \| help	0