제출 #645525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645525		SuchPigeon	Knapsack (NOI18_knapsack)	C++17	73 / 100	1079 ms	384 KiB

knapsack

    #include <bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
     
    const int LIM = 2000;
    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;
     
    	for(int i = 0; i < n; i++) {
    		cin >> v >> w >> k;
    		//fill(dp[1], dp[1]+LIM+1, 0);
    		//memcpy(dp[1], dp[0], sizeof(ll)*(LIM+1));
     
    		for(int j = w; j <= LIM; j++) {
    			for(ll t = 1; t <= k; t++) {
    				if(t*w > j) break;
				/*
				if(dp[0][j-t*w]+t*v < dp[1][j]) break;
				dp[1][j] = dp[0][j-t*w]+t*v;
				*/

    				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)*(s+1));
    	}
     
    	cout << dp[0][s] << '\n';
    }

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