제출 #1314761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314761		chirantan24	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	332 KiB

knapsack

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

int helper(vector<unordered_map<int,long long>>&dp,int i,long long w,int n,vector<long long>&values,vector<long long>&weights){
    if(w == 0){
        return 0;
    }
    if( i == n)
        return 0;
    if(dp[i].count(w))
        return dp[i][w];
    int a = helper(dp,i+1,w,n,values,weights);
    int b = w >= weights[i] ? helper(dp,i+1,w - weights[i],n,values,weights) + values[i]: 0;
    return dp[i][w] = max(a,b);
}
int main() {
	// your code goes here
    long long n,s;
    cin>>s>>n;
    vector<int>w(n),v(n),k(n);
    
    vector<long long>values,weights;
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i]>>k[i];
        long long sum = 0;
        for(int j=0;j<32;j++){
            if(sum + (1<<j) > k[i]){
                values.push_back((long long)v[i]*(long long)(k[i]-sum));
                weights.push_back((long long)w[i]*(long long)(k[i]-sum));
                break;
            }
            sum += (1<<j);
            values.push_back((long long)v[i]*(long long)(1<<j));
            weights.push_back((long long)w[i]*(long long)(1<<j));
        }
    }
    int ans = 0;
    int m = values.size();
    vector<long long>dp(s+1,0);
    for(int i=n-1;i>=0;i++){
      for(int j=s;j>=0;j--){
        if(j >= w[i]){
          dp[j] += dp[j-w[i]] + v[i];
        }
      }
    }
    cout<<dp[s];
}

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