oj.uz

답안 #437232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437232 2021-06-26T05:43:40 Z darkkcyan Knapsack (NOI18_knapsack) C++17
73 / 100
 1000 ms 460 KB 
#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 ll inf = 1e16;
const int max_s = 2020;

struct StaticDeque {
    int data[max_s * 10];
    int *head, *tail;
    
    StaticDeque() {
        clear();
    }
    
    void clear() {
        head = tail = data + max_s * 5;
    }
    
    size_t size() const {
        return tail - head;
    }
    
    void push_back(int num) {
        *tail++ = num;
    }
    
    void pop_back() {
        --tail;
    }
    
    void pop_front() {
        ++head;
    }
    
    int front() const { return *head; }
    int back() const { return tail[-1]; }
};

int main() {
#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;
    cin >> s >> n;
    vector<ll> dp(s + 1, -inf);
    dp[0] = 0;
    
    while (n--) {
        ll v;
        int w, k;
        cin >> v >> w >> k;
        
        vector<ll> new_dp = dp;
        rep(i, 0, s + 1) dp[i] -= v * (i / w);
        
        rep(rem, 0, w) {
            static StaticDeque qu;
            qu.clear();
            for (int i = rem; i <= s; i += w) {
                while (qu.size() and (i - qu.front()) / w > k) qu.pop_front();
                while (qu.size() and (dp[qu.back()] <= dp[i])) qu.pop_back();
                qu.push_back(i);
                new_dp[i] = max(new_dp[i], dp[qu.front()] + v * (i / w));
            }
        }
        swap(dp, new_dp);
    }
    
    cout << *max_element(all(dp));
    
    return 0;
}

// vim: foldmethod=marker

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 4 ms 332 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 6 ms 332 KB Output is correct
13 Correct 6 ms 360 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 4 ms 332 KB Output is correct
17 Correct 4 ms 460 KB Output is correct
18 Correct 4 ms 332 KB Output is correct
19 Correct 4 ms 332 KB Output is correct
20 Correct 4 ms 456 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 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 6 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 4 ms 332 KB Output is correct
13 Correct 3 ms 344 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 332 KB Output is correct
17 Correct 6 ms 360 KB Output is correct
18 Correct 3 ms 332 KB Output is correct
19 Correct 3 ms 332 KB Output is correct
20 Correct 4 ms 332 KB Output is correct
21 Correct 4 ms 460 KB Output is correct
22 Correct 4 ms 332 KB Output is correct
23 Correct 4 ms 332 KB Output is correct
24 Correct 4 ms 456 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 5 ms 332 KB Output is correct
27 Correct 6 ms 332 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 4 ms 332 KB Output is correct
30 Correct 4 ms 332 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 4 ms 332 KB Output is correct
33 Correct 4 ms 332 KB Output is correct
34 Correct 4 ms 332 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 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 6 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 4 ms 332 KB Output is correct
13 Correct 3 ms 344 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 332 KB Output is correct
17 Correct 6 ms 360 KB Output is correct
18 Correct 3 ms 332 KB Output is correct
19 Correct 3 ms 332 KB Output is correct
20 Correct 4 ms 332 KB Output is correct
21 Correct 4 ms 460 KB Output is correct
22 Correct 4 ms 332 KB Output is correct
23 Correct 4 ms 332 KB Output is correct
24 Correct 4 ms 456 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 5 ms 332 KB Output is correct
27 Correct 6 ms 332 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 4 ms 332 KB Output is correct
30 Correct 4 ms 332 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 4 ms 332 KB Output is correct
33 Correct 4 ms 332 KB Output is correct
34 Correct 4 ms 332 KB Output is correct
35 Correct 30 ms 324 KB Output is correct
36 Execution timed out 1091 ms 332 KB Time limit exceeded
37 Halted 0 ms 0 KB -