Submission #716629

#	Time	Username	Problem	Language	Result	Execution time	Memory
716629		farica	Knapsack (NOI18_knapsack)	C++14	100 / 100	159 ms	35088 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long

using namespace std;

typedef vector<int> vi;

const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1e9+7;
const int MAX_N = 1e6;
const int MAX_N2 = 1e5;
const int TWO_MOD_INV = 500000004;
const int M = 998244353;

void solve() {
    int n,s;
    cin >> s >> n;
    map<int, vector<pair<int,int>>>ma;
    for(int i=0; i<n; ++i) {
        int val, weight, am;
        cin >> val >> weight >> am;
        if(weight<=s && am) ma[weight].push_back({val, am});
    }
    vector<vector<ll>>dp(ma.size()+1, vector<ll>(s+1, INT32_MIN));
    dp[0][0]=0;
    int pos=1;
    for(auto &[w, items]: ma) {
        sort(items.begin(), items.end(), greater<pair<int,int>>());
        for(int i=0; i<=s; ++i) {
            dp[pos][i]=dp[pos-1][i];
            int cnt=0, num=0, us=0;
            ll profit=0;
            while(cnt<items.size() && w*(num+1)<=i) {
                ++num;
                profit+=items[cnt].first;
                if(dp[pos-1][i-w*num]!=INT32_MIN) dp[pos][i]=max(dp[pos][i], dp[pos-1][i-w*num]+profit);
                ++us;
                if(items[cnt].second==us) {
                    ++cnt;
                    us=0;
                }
            }
        }
        ++pos;
    }
    cout << *max_element(dp.back().begin(), dp.back().end()) << endl;
}

int main()
{

    //freopen("feast.in","r",stdin);
    //freopen("feast.out","w",stdout);

    int t=1;
    while(t--) solve();

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:28:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for(auto &[w, items]: ma) {
      |               ^
knapsack.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             while(cnt<items.size() && w*(num+1)<=i) {
      |                   ~~~^~~~~~~~~~~~~

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