제출 #975002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975002		vjudge1	Knapsack (NOI18_knapsack)	C++17	29 / 100	1 ms	1368 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define rep(i, n) for(int i = 0 ; i < n ; i++)
#define all(a) a.begin(), a.end()

// subsoal 1 & 2

int main() {
    fast

    int s, n; cin>>s>>n;
    int v[n+1], w[n+1], k[n+1];
    rep(i, n){
        cin>>v[i]>>w[i]>>k[i];
    }
    if(n == 1){
        int max = s/w[0];
        if(max > k[0]){
            cout<<v[0]*k[0];
            return 0;
        } else{
            cout<<v[0]*max;
            return 0;
        }
    } else{
        int dp[n+1][s+1];
        rep(i, s+1) dp[0][i] = 0;
        for(int i = 1 ; i<=n ; i++){
            for(int j = 0 ; j<=s ; j++){
                if(w[i-1] > j){
                    dp[i][j] = dp[i-1][j];
                } else{
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
                }
            }
        }
        cout<<dp[n][s];
    }
    
    return 0;
}

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