Submission #437351

#	Time	Username	Problem	Language	Result	Execution time	Memory
437351		darkkcyan	Knapsack (NOI18_knapsack)	C++17	100 / 100	869 ms	2484 KiB

knapsack

// #define gen_test               
// #pragma GCC optimize ("O3") 
// #pragma GCC optimize ("unroll-loops") 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
const ld eps = 1e-8;
// for matching the kactl notes
#define sz(x) ((int)x.size())
#define rep(i,a,b) for (int i = (int)(a); i < (int)(b); ++i) 
#define all(a) (a).begin(), (a).end()
// #define constexpr(...) (__VA_ARGS__)  
// DEBUGING TEMPLETE ////////////////////////////////////////////////////////////////////////{{{
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG   
#   define clog cerr << flush << string(__db_level * 2, ' ')
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
        debug_block() { clog << "{" << endl; ++__db_level; }
        ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif

template<class U, class V> ostream& operator<<(ostream& out, const pair<U, V>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}

template<class ...U> ostream& operator<<(ostream& out, const tuple<U...>& tup) {
    return print_tuple_utils<0, tuple<U...>>(out, tup);
}

template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& container) { 
    out << "{";
    for (auto it = container.begin(); it != container.end(); ++it)
        out << (it == container.begin() ? "" : ", ") << *it;
    return out << "}";
}
// ACTUAL SOLUTION START HERE ////////////////////////////////////////////////////////////////}}}

const int inf = 21e8;
const int max_s = 2048;

template<class T>
struct StaticDeque {
    T data[max_s * 16];
    T *head, *tail;
    
    StaticDeque() {
        clear();
    }
    
    inline void clear() {
        head = tail = data;
    }
    
    inline size_t size() const {
        return tail != head;
    }
    
    inline void push_back(T num) {
        *tail++ = num;
    }
    
    inline void pop_back() {
        --tail;
    }
    
    inline void pop_front() {
        ++head;
    }
    
    inline T front() const { return *head; }
    inline T back() const { return tail[-1]; }
};

#define getchar() getchar_unlocked()
inline void get_num(int& a) {
    int c; 
    while (!isdigit(a = getchar())); 
    a -= '0'; 
    while (isdigit(c = getchar())) { 
        a = a * 10 + c - '0'; 
    } 
    // int num; 
    // scanf("%d", &num); 
    // return num; 
}

int dp_data[2][max_s];

StaticDeque<int> qu;

mt19937 rng;
#define rand() ((int)(rng() >> 1))
int main() {
    // precal(); 
#ifdef LOCAL
    freopen("main.inp", "r", stdin); 
    freopen("main.out", "w", stdout);  
    freopen(".log", "w", stderr);
#endif
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int s, n;
#ifndef gen_test
    // cin >> s >> n; 
    get_num(s); get_num(n);
#else 
    s = 2000;
    n = 100000;
#endif
    int *dp = dp_data[0], *new_dp = dp_data[1];
    rep(i, 1, s + 1) {
        new_dp[i] = dp[i] = -inf;
    }
    
    while (n--) {
        int v;
        int w;
        int k;
#ifndef gen_test
        // cin >> v >> w >> k; 
        get_num(v); get_num(w); get_num(k);
#else
        v = rand() % 1000000 + 1;
        w = (short)(rand() % s + 1);
        k = rand() % ((int)1000000000) + 1;
#endif
        
        int dist;
        if (k > s / w + 10) dist = INT_MAX;
        else dist = k * w;
        if (dist == INT_MAX) {
            rep(rem, 0, w) {
                int cur_max = -inf;
                int div = 0;
                for (int i = rem; i <= s; i += w, div += v) {
                    if (dp[i] >= 0) dp[i] -= div;
                    cur_max = max(cur_max, dp[i]);
                    if (cur_max == -inf) {
                        new_dp[i] = -inf; 
                    }
                    else new_dp[i] = cur_max + div;
                }
            }
        } else {
            rep(rem, 0, w) {
                qu.clear();
                int div = 0;
                for (int i = rem; i <= s; i += w, div += v) {
                    if (dp[i] >= 0) dp[i] -= div;
                    while (qu.size() and (dp[qu.back()] <= dp[i])) qu.pop_back();
                    qu.push_back(i);
                    if (i - qu.front() > dist) qu.pop_front();
                    int x = dp[qu.front()];
                    if (x == -inf) {
                        new_dp[i] = -inf; 
                    }
                    else new_dp[i] = x + div;
                }
            }
        }
        swap(dp, new_dp);
    }
    
    cout << *max_element(dp, dp + s + 1);
    
    return 0;
}

// vim: foldmethod=marker

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