Submission #1195910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195910		Nonbangkok	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	2632 KiB

knapsack

#include <bits/stdc++.h>
#define coutf(n, m) cout << fixed << setprecision(n) << m
#define forr(i, a, n) for (int i = a; i < n; i++)
#define forl(i, a, n) for (int i = a; i > n; i--)
#define macos ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endll "\n"
#define sp " "
typedef long long ll;
using namespace std;

const int N = 1e5 + 10, M = 2e3 + 10;
ll s,n,mx;
ll v[N],w[N],x[N],dp[M];

int main(){macos;

    cin >> s >> n;
    forr(i,1,n+1)cin >> v[i] >> w[i] >> x[i];
    forr(i,1,n+1)forl(j,s,w[i]-1)forr(k,1,x[i]+1)
        if(j>=w[i]*k)dp[j] = max(dp[j],dp[j-w[i]*k]+v[i]*k),mx = max(mx,dp[j]);
        else break;

    cout << mx;

    return 0;
}

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