Submission #437353

# Submission time Handle Problem Language Result Execution time Memory
437353 2021-06-26T07:59:04 Z darkkcyan Knapsack (NOI18_knapsack) C++17
100 / 100
839 ms 460 KB
// #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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 3 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 3 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 5 ms 204 KB Output is correct
36 Correct 839 ms 332 KB Output is correct
37 Correct 789 ms 332 KB Output is correct
38 Correct 635 ms 332 KB Output is correct
39 Correct 353 ms 332 KB Output is correct
40 Correct 378 ms 332 KB Output is correct
41 Correct 754 ms 332 KB Output is correct
42 Correct 766 ms 460 KB Output is correct
43 Correct 751 ms 332 KB Output is correct
44 Correct 740 ms 332 KB Output is correct
45 Correct 372 ms 324 KB Output is correct
46 Correct 340 ms 324 KB Output is correct
47 Correct 365 ms 316 KB Output is correct
48 Correct 372 ms 332 KB Output is correct
49 Correct 341 ms 332 KB Output is correct
50 Correct 341 ms 332 KB Output is correct