Submission #1258015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258015		yazan112233	Knapsack (NOI18_knapsack)	C++20	0 / 100	1094 ms	320 KiB

knapsack

#include <bits/stdc++.h>
#define pb push_back
#define sz size()
#define ff first
#define ss second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define whatis(x) cout << #x << " is " << x << endl
using namespace std;
typedef long long ll;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
const ll mod = 1e9 + 7;
ll fp(ll x, ll y)
{
    if(y == 0) return 1;
    ll a = fp(x, y/2);
    a = (a * a) % mod;
    if(y & 1) a = (a * x) % mod;
    return a;
}
//ll comb(ll n, ll r)
//{
//    return (fact[n] * fp((fact[r] * fact[n-r]) % mod, mod - 2)) % mod;
//}
ll nxt()
{
    ll x;
    cin >> x;
    return x;
}
int dp[1000100];

void solve()
{
    int s,n;
    cin >>s>>n;
    int v[n];
    int w[n];
    int k[n];
    for (int i=0;i<n;i++){
        cin >>v[i]>>w[i]>>k[i];
    }
    for (int i=0;i<n;i++){
            for(int o=0;o<k[i];o++)
            for (int j=s;j>0;j--){
                if(j-w[i]>0)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

            }
    }
  cout <<dp[s];
}
int main()
{
    int T = 1;
   // cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}

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