Submission #1285477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285477		shine	Knapsack (NOI18_knapsack)	C++17	100 / 100	518 ms	48772 KiB

knapsack

//--------------------------------- 
#include <bits/stdc++.h>
using namespace std;

//---------------------------------
#ifdef DEBUG
#define debug(x) {cout<<"---> "<<#x<<" = "<<x<<endl;}
#else
#define debug(x)
#endif 
//--------------------------------- 
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// #define int long long
#define ff first
#define ss second
#define endl "\n"
#define pii pair<int,int>
#define REP(a, c) for (int(a) = 0; (a) < (c); (a)++)
#define FOR(a, b, c) for (int(a) = (b); (a) <= (c); (a)++)
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
#define tpl tuple<int,int,int> 
#define ld long double 
#define subtract(x) ((~(x)) ^ (1 << __builtin_ctz(x) + 1) - 1)
//---------------------------------
#define _task "TASK"
inline void _FILE() {
    if(fopen(_task ".inp", "r")) {
        freopen(_task ".inp", "r", stdin);
        freopen(_task ".out", "w", stdout);
    }
}
//---------------------------------
const int maxK = 1e3 + 5;
const int maxL = 1e4 + 5;
const int maxM = 1e5 + 5;
const int maxN = 1e6 + 5;
const int maxP = 1e7 + 5;
const long long inf = 1e18;
const int mod = 1e9 + 7;
//---------------------------------
int n, S, dp[2005];
struct th{
    int v, w, k;
} a[maxN];
multiset<int, greater<int>> mp[2005];
vector<pii> p; 
signed main()
{   
    faster
    _FILE();
    cin >> S >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].v >> a[i].w >> a[i].k;
        a[i].k = min(a[i].k, 2000);
        int cnt = 1, currv = a[i].v, currw = a[i].w;
        while(cnt <= a[i].k && currw <= S){
            a[i].k -= cnt;
            mp[currw].insert(currv); 
            currv *= 2, currw *= 2;
            cnt *= 2;
        }
        if(a[i].k && a[i].k * a[i].w <= S){
            mp[a[i].w * a[i].k].insert(a[i].v * a[i].k); 
        }
    }
    for(int i = 0; i <= S; i++){
        dp[i] = -mod * 2;
        int cnt = 0;
        for(auto v : mp[i]){
            // debug(v)
            cnt++;
            p.push_back({v, i});
            if(cnt * i > S) break;
        }
    } 
    dp[0] = 0;
    for(auto v : p){
        // cout << v.ff << ' ' << v.ss << endl;
        for(int s = S; s >= v.ss; s--){
            dp[s] = max(dp[s], dp[s - v.ss] + v.ff);
        }
    }
    int ans = 0;
    for(int i = 0; i <= S; i++){
        ans = max(ans, dp[i]);
    }
    cout << ans;
    #ifndef ONLINE_JUDEGE
        cerr << "Time elapsed: " << clock() * 1.0 / CLOCKS_PER_SEC << "s.\n";
    #endif
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void _FILE()':
knapsack.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(_task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(_task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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