Submission #519672

#	Time	Username	Problem	Language	Result	Execution time	Memory
519672		Trent	Knapsack (NOI18_knapsack)	C++17	73 / 100	164 ms	262148 KiB

knapsack

#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
#include <set>
#include <string>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>


using namespace std;
#define ll long long
#define ull unsigned ll
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
void assert(bool a) { if (!a)throw; }
#define open(g) string _name_ = g; freopen((_name_ + ".in").c_str(), "r", stdin); freopen((_name_ + ".out").c_str(), "w", stdout)
#define printArr(a, len) for(int asdasf = 0; asdasf < (len); ++asdasf) cout << (a)[asdasf] << ' '; cout << '\n';
#define print2Arr(a, d1, d2) for(int asdfsad = 0; asdfsad < (d1); ++asdfsad){ for(int asjk = 0; asjk < (d2); ++asjk) cout << a[asdfsad][asjk] << ' '; cout << '\n'}
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define REPI(i, a, b, d) for(int i = (a); i < (b); i += (d))
#define pii pair<int, int>
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define mii map<int, int>
#define umii unordered_map<int, int>
#define int ll

const int MN = 1e5 + 10, MS = 2010;
int dp[MN][MS];
int val[MN], we[MN], cnt[MN];

signed main() {
    int s, n;
    cin >> s >> n;
    forR(i, n) cin >> val[i] >> we[i] >> cnt[i];
    REP(i, we[0], s + 1) dp[0][i] = val[0] * min(cnt[0], i / we[0]);
    REP(i, 1, n){
        for(int start = 0; start < we[i]; ++start){
            deque<pii> stk; // [{val, ind}, ...]
            for(int cur = start, off=0; cur <= s; cur += we[i], off += val[i]){
                int comp = dp[i - 1][cur] - off;
                while(!stk.empty() && stk.back().first < comp) stk.pop_back();
                while(!stk.empty() && stk.front().second < cur - we[i] * cnt[i]) stk.pop_front();
                stk.push_back({comp, cur});
                dp[i][cur] = stk.front().first + off;
            }
        }
    }
    int ma = 0;
    forR(i, s + 1) ma = max(ma, dp[n - 1][i]);
    cout << ma << '\n';
}

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