Submission #706007

#	Time	Username	Problem	Language	Result	Execution time	Memory
706007		lukameladze	Knapsack (NOI18_knapsack)	C++14	100 / 100	80 ms	30808 KiB

knapsack

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 1e6 + 5;
int t,n,w[N],s,sum[N],dp[N],v[N],k[N];
vector <pii> vec[N];
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>s>>n;
    for (int i = 1; i <= n; i++) {
        cin>>v[i]>>w[i]>>k[i];
        vec[w[i]].pb({v[i], k[i]});
        sum[w[i]] += k[i];
    }
    int ans = 0;
    for (int i = 1; i <= s; i++) {
        sort(vec[i].rbegin(),vec[i].rend());
        int cur = 0, cnt = 0;
        for (int j = 1; j <= min(s / i, sum[i]); j++) {
            for (int k = s; k >= i; k--) {
                dp[k] = max(dp[k], dp[k - i] + vec[i][cur].f);
                ans = max(ans, dp[k]);
            }
            cnt++;
            if (cnt == vec[i][cur].s) cur++, cnt = 0;
        }
    }
    cout<<ans<<"\n";
}

Compilation message (stderr)

knapsack.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main() {
      | ^~~~

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