제출 #1126991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126991		himanshu_03	Knapsack (NOI18_knapsack)	C++17	37 / 100	1095 ms	1864 KiB

knapsack

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

//cycle edges = total edges-bridge edges
// adding cycle edges does not decrease the number of disconnected component but bridge edges do
// decreasing order of weight of edges . adding using dsu -> edges whoes parent already in the component is the cycle edges->can be found the min. weight prsent in cycle


const int md=1e9+7;
int main()
{
    int s,n;
    cin>>s>>n;
    vector<int> val(n+1),we(n+1),no(n+1);
    for(int i=1;i<=n;i++){
        cin>>val[i]>>we[i]>>no[i];
    }
    vector<vector<long> > dp(n+1,vector<long>(s+1,0));

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=s;j++)
        {
            dp[i][j]=dp[i-1][j];
            
            for(int k=0;k<no[i];k++){
                if(j>=(k+1)*we[i]){
                    dp[i][j]=max(dp[i][j],dp[i-1][j-(k+1)*we[i]]+(k+1)*val[i]);
                }
            }
        }
    }

    cout<<dp[n][s]<<endl;
   
  

    


   
    
   


    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27