Submission #657219

#	Time	Username	Problem	Language	Result	Execution time	Memory
657219		_BONK_	Knapsack (NOI18_knapsack)	C++14	73 / 100	652 ms	262144 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];
        f(i,0,n+1){
            f(j,0,s+1) dp[i][j] = -1;
        }
        cout<<recurse(0, s, v, w, k, n);
    }
    return 0;
}

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