제출 #1220254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220254		crazygautam	Knapsack (NOI18_knapsack)	C++20	73 / 100	1088 ms	456 KiB

knapsack

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

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pl;
typedef vector<vector<ll>> vvl;
typedef set<ll> sl;
typedef vector<string> vs;
typedef set<string> ss;
typedef multiset<string> mss;
typedef map<ll, ll> mll;
typedef unordered_set<ll> usl;
typedef deque<ll> dql;
typedef unordered_map<ll, ll> umll;
typedef set<ll> sl;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define SQ(a) (a) * (a)
#define vb vector<bool>
#define pll pair<ll, ll>
#define fast                     \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);
#define print_vec(vec)     \
    for (auto it : vec)    \
    {                      \
        cout << it << " "; \
    }
#define print(string) cout << string << endl;
#define all(v) v.begin(), v.end()
const ll MOD = 1e9+7;

ll ncr(ll n, ll r)
{
    if (r == 0 || r == n)
        return 1;
    if (r == 1)
        return n;
    ll prev = ncr(n - 1, r - 1);
    return (n * prev) / r;
}

vector<ll> sieveOfEratosthenes(ll upper_limit)
{
    vector<ll> is_prime(upper_limit + 1, 1);
    is_prime[0] = is_prime[1] = 0;
    for (ll i = 2; i * i <= upper_limit; i++)
    {
        if (is_prime[i])
        {
            for (ll j = i * i; j <= upper_limit; j += i)
            {
                is_prime[j] = 0;
            }
        }
    }
    return is_prime;
}


int power(int a, int b) {
    int res = 1;
    while(b) {
        if(b&1) res = (1LL * res * a) % MOD;
        a = (1LL * a * a) % MOD;
        b >>= 1;
    }
    return res;
}



void solve() {
    ll s, n;
    cin >> s >> n;
    vector<ll> dp(s + 1, 0);

    for (ll i = 0; i < n; i++) {
        ll value, weight, count;
        cin >> value >> weight >> count;

        for (ll k = 1; count > 0; k <<= 1) {
            ll use = min(k, count);
            ll total_val = use * value;
            ll total_wt = use * weight;

            for (ll j = s; j >= total_wt; j--) {
                dp[j] = max(dp[j], dp[j - total_wt] + total_val);
            }

            count -= use;
        }
    }

    cout << dp[s] << endl;
}

signed main()
{
    fast
    // freopen("maxcross.in", "r", stdin);
    // freopen("maxcross.out", "w", stdout);

    // ll t = 1;
    // cin >> t;
    // while (t--)
    // {
    //     solve();
    // }
    solve();

    // Solution sol;
    // sol.numberOfPaths();

    return 0;
}

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