Submission #735243

#	Time	Username	Problem	Language	Result	Execution time	Memory
735243		danilovict2	Knapsack (NOI18_knapsack)	C++14	73 / 100	144 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
    using namespace std;
     
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define pii pair<int, int>
    #define vi vector<int>
    #define vii vector<pair<int, int>>
    #define mp make_pair
    #define sz(a) a.size()
    #define MOD 1000000007
    #define forn(i, n) for (int i = 0; i < n; ++i)
    #define INF 1e18
    const vector<pair<int, int>> dirs1 = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    const vector<pair<int, int>> dirs2 = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) { return (a.second < b.second); }
    const int maxN = 100001;
     
    int dp[maxN][2001];
     
    void solve(){
    	int n,s;
    	cin>>s>>n;
    	int v[n], w[n], k[n];
    	forn(i,n){
    		cin>>v[i]>>w[i]>>k[i];
    	}
    	dp[0][0] = 0;
    	for(int i=1;i<=n;++i){
    		for(int j=1;j<=s;++j){
    			dp[i][j] = dp[i-1][j];
    			for(int t=1;t<=k[i-1];++t){
    				if(j >= t*w[i-1])dp[i][j] = max(dp[i][j], dp[i-1][j-t*w[i-1]] + v[i-1]*t);
    				else break;
                }
    		}
    	}
    	cout<<dp[n][s]<<"\n";
    }
     
    int main(void){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    	solve();
    	return 0;
    }

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