Submission #1193100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193100		joue-zero	Knapsack (NOI18_knapsack)	C++20	73 / 100	1092 ms	1608 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename... Args> ostream& operator<<(ostream& os, const tuple<Args...>& t) { os << '('; apply([&os](const Args&... args) { size_t n = 0; ((os << args << (++n != sizeof...(Args) ? ", " : "")), ...); }, t); return os << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef JOE_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
const ll N = 2999 + 1, M = 1e9 + 7;
string s, t;
ll n, m, q, k, x, y, c;
ll mul(ll a, ll b) {
    return (a % M) * (b % M) % M;
}
ll add(ll a, ll b) {
    return (a % M + b % M) % M;
}
void solve() {
    int s;
    cin >> s >> n;
    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];
    ll dp[s+1];
    memset(dp,0,sizeof dp);
    for (int i = 0; i < n; i++) {
        int limit = c[i],
            factor = 1,
            take = 0;
        while (limit) {
            take = min(factor, limit);
            for (ll j = s; j >= take *1ll* b[i]; j--) {
                dp[j] = max(a[i]*1ll*take + dp[j-take*b[i]], dp[j]);
            }
            limit -= take;
            factor *= 2;
        }
    }
    cout << dp[s] << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
#ifdef JOE_DEBUG
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#endif
    int tt = 1;
    // cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

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