Submission #1119737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119737		vjudge1	Knapsack (NOI18_knapsack)	C++17	37 / 100	294 ms	262144 KiB

knapsack

          /////////////////////////////////////////////////////////////////
         ////////            Born_To_Laugh - Hughie Do            ////////
        /////////////////////////////////////////////////////////////////
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=3e5+5;
const int INF=1e9+7;
/*
    Idea:
*/
void solve(){
    int t ,s;
    cin >> s >> t;
    vector<pair<int,int>> items;
    items.push_back({0,0});
    int n=0;
    while(t--){
        int w, v ,k;
        cin >> v >> w >> k;
        n+=k;
        while(k--){
            items.push_back({w,v});
        }
    }
    sort(items.begin(), items.end());
    vector<vector<int>> dp(n+1, vector<int> (s+1, 0));
    /*
        dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
    */
    for(int i=1; i<=n; ++i){
        for(int j=0; j<=s; ++j){
            if(j-items[i].first >= 0){
                dp[i][j]=max(dp[i-1][j], dp[i-1][j-items[i].first] + items[i].second);
            }
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout << dp[n][s];

}
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}




















































































/*
    Use for suggestion:
    {
        while
    }
    {
        nullptr
        sync_with_stdio
        false
        return
        to_string
        length
    }
    {
        push_back
        pop_back
        sort
        reverse
        begin
        end
        distance
        assign 
    }
    {
        insert
        erase
        lower_bound
        upper_bound
        binary_search
        
    }
    {
        first   
        second
        swap
    }
    {
        double
        float
        unsigned
    }
    {
        unordered_map
        pair
        vector
        deque
        string
        auto
        cout
    }
*/

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