Submission #1304316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304316		s3yoonpark	Knapsack (NOI18_knapsack)	C++20	73 / 100	191 ms	280024 KiB

knapsack

#include <bits/stdc++.h>
using namespace std; 
#define int long long 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

void solve() 
{
    int n, s; 
    cin >> s >> n; 
    vector<int> price(n + 1), page(n + 1), num(n + 1); 
    vector mp(s + 1, vector<pair<int,int>>{});
    for (int i = 1; i <= n; i++) 
    {
        cin >> page[i] >> price[i] >> num[i]; 
        mp[price[i]].emplace_back(page[i], num[i]); 
    } 
    
    vector<int> newPrice; 
    vector<int> newPage; 
    for (int i = 1; i <= s; i++)
    {
        sort(mp[i].rbegin(), mp[i].rend()); 
        int cnt = 1; 
        for (auto [a, b] : mp[i])
        {
            for (int it = 1; it <= b; it++)
            {
                newPrice.push_back(i); 
                newPage.push_back(a); 
                ++cnt; 
                if (cnt == (s + i - 1) / i + 1) break; 
            }
            if (cnt == (s + i - 1) / i + 1) break; 
        }
    }

    int m = newPrice.size(); 
    newPrice.insert(newPrice.begin(), 0); 
    newPage.insert(newPage.begin(), 0); 

    vector dp(m + 1, vector<int>(s + 1, 0)); 

    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            dp[i][j] = dp[i - 1][j]; 
            if (j >= newPrice[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - newPrice[i]] + newPage[i]); 
        }
    }

    cout << dp[m][s] << '\n'; 
}   

signed main() 
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    int tc = 1;
    // cin >> tc; 
    while (tc--) solve(); 
    return 0; 
}

//  dp[i][j] = maximum number of pages i can buy having bought considering first i distinct books and with j money
//  dp[i][j] = dp[i - 1][j - (0..k[i]) * h[i]] + (0..k[i]) * s[i] 
//  dp[i - 1][ j - (0...k[i]) * h[i] ] + (0...k[i]) * s[i]  

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