Submission #657223

#	Time	Username	Problem	Language	Result	Execution time	Memory
657223		_BONK_	Knapsack (NOI18_knapsack)	C++14	73 / 100	1086 ms	4040 KiB

knapsack

#include <bits/stdc++.h>
#include <unordered_map>
#define ull unsigned long long 
#define ul unsigned long
#define ll long long
#define pb push_back
#define sodayoda_C  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define f(i,a,b) for(int i = a;i<b;i++)
#define fb(i,a,b) for(int i = a;i>b;i--)
#define endl "\n"
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define MP make_pair
#define F first
#define S second
typedef std::vector<int> vi;
typedef std::pair<int, int> pi;
#define mod 1000000007
//memset(name,'',size)
//reverse(s,begin(),s.end())

using namespace std;

// ll dp[100001][2001];

// ll recurse(int i, int s, ll v[], ll w[], ll k[], int n){
//     if(i == n) return 0;
//     if(dp[i][s] != -1) return dp[i][s];
//     ll ans = 0;
//     for(int j = 0;j<=k[i];j++){
//         if(s - j*w[i] >= 0) ans = max(ans, j*v[i] + recurse(i+1, s-j*w[i], v, w, k, n));
//         else break;
//     }
//     return dp[i][s] = ans;
// }

int main(){    
    sodayoda_C;
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif
    int t = 1;
    //cin>>t;
    while(t--){
        ll s, n;
        cin>>s>>n;
        ll v[n], w[n], k[n];
        f(i,0,n) cin>>v[i]>>w[i]>>k[i];
        //cout<<recurse(0, s, v, w, k, n);
        ll dp[s+1], DP[s+1];
        for(int i = 0;i<s+1;i++) DP[i] = 0;
        for(int i = n-1;i>=0;i--){
            for(int cs = 0;cs<s+1;cs++){
                dp[cs] = 0;
                for(int j = 0;j<=k[i];j++){
                    if(cs - j*w[i] >= 0) dp[cs] = max(dp[cs], j*v[i] + DP[cs - j*w[i]]);
                    else break;
                }
            }
            for(int cs = 0;cs<s+1;cs++){
                DP[cs] = dp[cs];
            }
        }
        cout<<dp[s]<<endl;
    }
    return 0;
}

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