Submission #1290214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290214		s0me0ne	Knapsack (NOI18_knapsack)	C++20	37 / 100	1102 ms	154128 KiB

knapsack

#pragma optimise GCC "O3" //o3 is imporant, removes unused functions
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
const ll LLMAX = 2147483648;
#define tt true
#define ff false
/*--------------guide-----------
 * us = unsigned
 * uo = unordered
 * v = vector<>
 * ms = multiset
 * s(first) = set
 * s(after) = short
 * m = map
 * i = int
 * l = long long
 * vv = vector<vector<>>
 * ii = pair<int,int>
 * ll = pair<long long, long long>
 * sz = sets size 
 * vsort / rvsort = sorts a vector in ascending (vsort) or descending (rvsort) order
 * tmax = max function that supports comparing two variable types
 * tmin = tmax but min
 * smax / smin = tmax/tmin but it sets the FIRST input to the result of the min/max
-------------------------------*/

#define us unsigned
#define vi vector <int>
#define vvi vector <vi>
#define vii vector <pair <int,int>>
#define vl vector <ll>
#define vvl vector <vl>
#define vll vector <pair <ll,ll>>
#define vvlsz(x, y) (x, vector <ll> (y))
#define vvisz(x, y) (x, vector <int>(y))
#define vvlszst(x, y, z) (x, vector <ll> (y, z))
#define vviszst(x, y, z) (x, vector <int>(y, z))
#define uosi unordered_set<int>
#define uosl unordered_set<ll>
#define si set<int>
#define sl set<ll>
#define msi multiset<int>
#define msl multiset<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mil map<int,ll>
#define mli map<ll,ii>
#define mmis map<int,short>
#define mmsi map<short,int>

#define vsort(x)  sort(x.begin(), x.end())
#define rvsort(x) sort(x.rbegin(), x.rend())

#define tmax(a, b) a>b ? a:b
#define tmin(a, b) a<b ? a:b
#define smax(a, b) a = a>b ? a:b
#define smin(a, b) a = a<b ? a:b
#define dsmax(a, b) a = max(a, b)
#define dsmin(a, b) a = min(a, b)

#define qc(x) for(auto &i:x)cin>>i

/*-----------------prewritten functions-----------------*/
static inline ll tmod(ll a,ll b){
    if(a>=0)return a%b;
    else return b-a%b;
}
bool isprime(ll a){
    if(a==2)return tt;
    if(a==1||a%2==0)return ff;
    for(ll i=3;i*i<=a;i+=2)if(a%i==0)return ff;
    return tt;
}
class monotonicStack{
    stack<int> k;
    void insert(int i){
        while(!k.empty() && k.top()<i)k.pop();
        k.push(i);
    }
    inline int top(){
        return k.top();
    }
};
class monotonicQueue{
    list<int>k;
    void push(int i){
        while(!k.empty() && k.back()<i)k.pop_back();
        k.push_back(i);
    }
    inline void pop(int i){if(!k.empty() && k.front()==i)k.pop_front();}
    inline int front(){return k.empty()?0:k.front();}
};
class DSU{
    static int root(int x, vector<int>&k) {return k[x]<0?x:k[x]=root(k[x],k);}
    bool join(int x, int y, vector<int>&k){
        x=root(x,k);
        y=root(y,k);
        if(x==y)return 0;
        k[x]+=k[y];
        k[y]=x;
        return true;
    }
};
/*-----------------problem-specific code-----------------*/
int main(){
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n,w;
    cin>>w>>n;
    //vector<vector<bool>>dp(n+1,vector<bool>(w+1,ff));
    vl dp(w+1,0);
    multiset <pair<ll, ll>> k;
    for(int i=0; i < n; i++){
        int a, b, c;
        cin>>a>>b>>c;
        while(c--) k.insert( {b, a} );
    }
    dp[0] = 0;
    ll ans = 0;
    for(auto i:k){
        for(int j = w; j >= 0; j--){
            if(j-i.first>=0) 
                dsmax(dp[j], dp[j - i.first] + i.second);
            //cout<<j<<' '<<i.second<<' '<<dp[j]<<endl;
        }
    }
    cout<<*max_element (dp.begin(), dp.end())<<endl;
    return 0;
}

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