oj.uz

Submission #437351

# Submission time Handle Problem Language Result Execution time Memory
437351 2021-06-26T07:56:41 Z darkkcyan Knapsack (NOI18_knapsack) C++17
100 / 100
 869 ms 2484 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

Subtask #1
12.0 / 12.0

# 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

Subtask #2
17.0 / 17.0

# 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 1 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 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct

Subtask #3
20.0 / 20.0

# 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 1 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 2 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 332 KB Output is correct
12 Correct 1 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 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 1 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct

Subtask #4
24.0 / 24.0

# 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 1 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 2 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 332 KB Output is correct
16 Correct 1 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 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 1 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 3 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 1 ms 336 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

Subtask #5
27.0 / 27.0

# 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 1 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 2 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 332 KB Output is correct
16 Correct 1 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 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 1 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 3 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 1 ms 336 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 3 ms 204 KB Output is correct
36 Correct 869 ms 332 KB Output is correct
37 Correct 811 ms 332 KB Output is correct
38 Correct 651 ms 312 KB Output is correct
39 Correct 353 ms 332 KB Output is correct
40 Correct 439 ms 312 KB Output is correct
41 Correct 766 ms 332 KB Output is correct
42 Correct 753 ms 1624 KB Output is correct
43 Correct 808 ms 1732 KB Output is correct
44 Correct 746 ms 1712 KB Output is correct
45 Correct 380 ms 2360 KB Output is correct
46 Correct 337 ms 2256 KB Output is correct
47 Correct 368 ms 2484 KB Output is correct
48 Correct 379 ms 2372 KB Output is correct
49 Correct 342 ms 2104 KB Output is correct
50 Correct 341 ms 2216 KB Output is correct