Submission #583790

#	Time	Username	Problem	Language	Result	Execution time	Memory
583790		jack715	Knapsack (NOI18_knapsack)	C++14	100 / 100	66 ms	3040 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});
    }


    for (int i = 1; i <= s; i++) {
        sort(nums[i].rbegin(), nums[i].rend());
        for (int j = 0; j < nums[i].size(); j++) {
            if (op[i].size() >= s/i) break;
            for (int k = 0; k < nums[i][j].ss && op[i].size() < s/i; k++) {
                op[i].pb(nums[i][j].ff);
            }
        }
    }

    int dp[2005], now;
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= s; i++) {
        for(int j = s; j >= 0; j--) {
            now = 0;
            for(int x = 1; x <= op[i].size(); 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:30:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int j = 0; j < nums[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
knapsack.cpp:31:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   31 |             if (op[i].size() >= s/i) break;
      |                 ~~~~~~~~~~~~~^~~~~~
knapsack.cpp:32:63: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   32 |             for (int k = 0; k < nums[i][j].ss && op[i].size() < s/i; k++) {
      |                                                  ~~~~~~~~~~~~~^~~~~
knapsack.cpp:44:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int x = 1; x <= op[i].size(); x++) {
      |                            ~~^~~~~~~~~~~~~~~

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