oj.uz

Submission #437350

# Submission time Handle Problem Language Result Execution time Memory
437350 2021-06-26T07:53:51 Z darkkcyan Knapsack (NOI18_knapsack) C++17
73 / 100
 1000 ms 332 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 272 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 2 ms 204 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 272 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 2 ms 204 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 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 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 3 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 3 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 272 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 3 ms 332 KB Output is correct
11 Correct 2 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 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 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
21 Correct 3 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 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 1 ms 332 KB Output is correct
28 Correct 2 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 2 ms 332 KB Output is correct
34 Correct 2 ms 332 KB Output is correct

Subtask #5
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 272 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 3 ms 332 KB Output is correct
11 Correct 2 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 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 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
21 Correct 3 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 3 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 1 ms 332 KB Output is correct
28 Correct 2 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 2 ms 332 KB Output is correct
34 Correct 2 ms 332 KB Output is correct
35 Correct 3 ms 204 KB Output is correct
36 Correct 873 ms 332 KB Output is correct
37 Correct 893 ms 332 KB Output is correct
38 Execution timed out 1087 ms 332 KB Time limit exceeded
39 Halted 0 ms 0 KB -