Submission #645515

#	Time	Username	Problem	Language	Result	Execution time	Memory
645515		SuchPigeon	Knapsack (NOI18_knapsack)	C++17	12 / 100	9 ms	596 KiB

knapsack

    #include <bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
     
    const int LIM = 20000;
    ll dp[2][LIM+1];
     
    int main() {
    	cin.tie(NULL);
    	ios_base::sync_with_stdio(false);
     
    	int s, n;
    	ll w,k;
    	ll v;
    	fill(dp[0], dp[0]+LIM+1, 0);
     
    	cin >> s >> n;
     
    	while(n--) {
    		cin >> v >> w >> k;
    		fill(dp[1], dp[1]+LIM+1, 0);
    		memcpy(dp[1], dp[0], w);
     
    		for(int j = w; j <= LIM; j++) {
    			for(ll t = 1; t <= k; t++) {
    				if(t*w > j) break;
    				dp[1][j] = max({dp[1][j], dp[0][j-t*w]+t*v, dp[1][j-1]});
    			}
    		}
    		memcpy(dp[0], dp[1], sizeof(ll)*(LIM+1));
    	}
     
    	cout << dp[0][s] << '\n';
    }

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