Submission #1286321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286321		efeg	Knapsack (NOI18_knapsack)	C++20	100 / 100	60 ms	34716 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#define int long long
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define pqueue priority_queue

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,string> tp;  

const int INF = 1e7 + 100;
const int MOD = 1e9 + 7;  
const int maxN = 3100;



void _(){   
    int s,n; 
    cin >> s >> n;
    vector<ii> a[s + 10];  
    for (int i = 0; i < n; i++){
        int v,w,k; cin >> v >> w >> k; 
        a[w].eb(v,k); 
    }

    vector<vector<int>> dp(s + 10,vector<int> (s+10,0)); 
    // dp[i][j] = i ye kadar maks j weight alarak yapılabilecek best score; 

    int mx = 0; 
    for (int i = 1; i <= s; i++){
        sort(all(a[i]),greater<ii>());
        for (int j = 0; j <= s; j++){
            dp[i][j] = max(dp[i][j],dp[i-1][j]); 
            if (a[i].empty()) continue; 
            int ptr = 0,add = 0,k = a[i][ptr].S,val = 0;   
            while (j + add + i <= s && ptr < a[i].size()){
                val += a[i][ptr].F;     
                add += i; 
                k--;
                dp[i][j + add] = max(dp[i][j + add],dp[i-1][j] + val);
                mx = max(mx,dp[i][j + add]); 
                if (k == 0){
                    ptr++; 
                    if (ptr == a[i].size()) break;
                    k = a[i][ptr].S; 
                }
            }
        }
    }

    cout << mx << endl; 


}

int32_t main(){	
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; // cin >> t;
    while (t--){
        _();
    }
    
    return 0;
}

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