Submission #887783

#	Time	Username	Problem	Language	Result	Execution time	Memory
887783		conthoanco	Knapsack (NOI18_knapsack)	C++14	100 / 100	76 ms	3156 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define II pair < int , int >
#define pb push_back
#define mset(a , b) memset(a , b , sizeof a)
#define all(a) (a).begin() , (a).end()
const int N = 1e5 + 5;
int s, n, v[N], w[N], k[N], dp[2][N];
vector<II> lst[2005], vc;
void input()
{
    cin >> s >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i] >> k[i];
        k[i] = min(k[i], s);
        lst[w[i]].pb({v[i], k[i]});
    }
}
void solve()
{
    vc.pb({0, 0});
    for(int i = 1; i <= s; ++i) {
        sort(lst[i].rbegin(), lst[i].rend());
        int lim = s / i;
        for(auto j: lst[i]) {
            if(lim == 0) break;
            int cur = min(lim, j.se);
            lim -= cur;
            while(cur--) vc.pb({j.fi, i});
        }
    }
    int res = 0;
    for(int i = 1; i < vc.size(); ++i) {
        for(int curS = 0; curS <= s; ++curS) {
            dp[i % 2][curS] = dp[1 - i % 2][curS];
            if(curS >= vc[i].se) dp[i % 2][curS] = max(dp[i % 2][curS], dp[1 - i % 2][curS - vc[i].se] + vc[i].fi);
            res = max(res, dp[i % 2][curS]);
        }
    }
    cout << res;
}
int main()
{
    if(fopen("trash.inp" , "r"))
        freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
    // else freopen(".inp" , "r" , stdin) , freopen(".out" , "w" , stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:35: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]
   35 |     for(int i = 1; i < vc.size(); ++i) {
      |                    ~~^~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:47:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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