Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Peg Grammar AST Parser Computer Language Interpreter
Microsoft - MaxEmployeeAttendence (R repititions - Optimised DP)
Median of row wise sorted matrix
Boost phoenix. e.g 2: functor
My Pratice
basic observation leads to dp OPTIMIZATION from O(n^3) to O(n^2) !!! (sopj : AMBLE)
lock
Switch case
A • Potato Sacks
Destroy It!