Submission #583797

#	Time	Username	Problem	Language	Result	Execution time	Memory
583797		jack715	Knapsack (NOI18_knapsack)	C++14	100 / 100	154 ms	1688 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
// #define int long long

using namespace std;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("tmp.in", "r", stdin);
    // freopen("tmp.out", "w", stdout);

    int s, n, a, b, c;
    cin >> s >> n;
    vector<vector<pair<int, int> > > nums(s+1);
    vector<vector<int> > op(s+1);
    for (int i = 0; i < n; i++) {       
        cin >> a >> b >> c;
        nums[b].pb({a, c});
    }


    int now;
    vector<int> dp(s+1, -1);
    for (int i = 1; i <= s; i++) {
        sort(nums[i].rbegin(), nums[i].rend());
        now = 0;
        op[i].resize(s/i);
        for (int j = 0; j < nums[i].size() && now < s/i; j++) {
            for (int k = 0; k < nums[i][j].ss && now < s/i; k++) {
                op[i][now] = nums[i][j].ff, now++;
            }
        }
    }

    dp[0] = 0;
    for (int i = 1; i <= s; i++) {
        for(int j = s; j >= 0; j--) {
            now = 0;
            for(int x = 1; x <= s/i; x++) {
                now += op[i][x-1]; 
                if(j - x * i < 0) break;
                dp[j] = max(dp[j], dp[j - x * i] + now);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= s; i ++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
    return 0; 
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:34:27: 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 |         for (int j = 0; j < nums[i].size() && now < s/i; j++) {
      |                         ~~^~~~~~~~~~~~~~~~

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