Submission #1290228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290228		s0me0ne	Knapsack (NOI18_knapsack)	C++20	100 / 100	38 ms	1932 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
const int maxn = 1e5+10;
/*--------------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-----------------*/
vector<pair <int, int>> k [maxn]; // vector is faster than map; mem isnt too big of an issue
int main(){
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n,w;
    cin>>w>>n;
    if(n==1){
        ll a,b,c;
        cin>>a>>b>>c;
        cout<<min(w/b,c)*a; // optimise fork 
        return 0;
    }
    //vector<vector<bool>>dp(n+1,vector<bool>(w+1,ff));
    vl dp(w+1,0);
    //vector <pair<ll, ll>> k;
    for(int i=0; i < n; i++){
        int a, b, c;
        cin>>a>>b>>c;
        smin(c,w/b);
        k[b].push_back( {a, c});
    }
    dp[0] = 0;
    vi kx, val;
    for(int i = 1; i <= w; i++){
        sort(k[i].begin(), k[i].end(), [] (pair<int, int> a, pair<int, int> b)
            {return a.first > b.first;});
        int cnt = 0;
        for(int j = 0; j < k[i].size(); j++){
            int a = k[i][j].first, b = k[i][j].second;
            if(cnt * i > w) break;
            for(int l = 1; l <= b;l++){
                if(cnt*i>w) break;
                cnt++;
                kx.push_back (i);
                val.push_back (a);
            }
        }
    }
    for(int i = 0; i < kx.size(); i++){
        for(int s = w; s >= kx[i]; s--)
            dp[s] = max(dp[s], dp[s-kx[i]] + val[i]);
    }
    ll ans = 0;
    for(int i = 1; i <= w; i++) ans = max(ans, dp[i]);
    cout<<ans;
    return 0;
}

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