Submission #1290874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290874		ssseul	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	584 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define el '\n'

const int maxN = 505;
const int base = 311;
const int MOD = 1e9+7;
const int INF = 1e15;
const int NEG_INF = -1e15;
const int MAX_DAYS = 1000;


int n, m, k, q;
string S, T, SS[maxN];
// int dp[maxN][maxN];
vector<int> g[maxN];

void run_test() {
    int S, N;
    cin >> S >> N;

    vector<long long> prev_dp(S + 1, 0); // dp[i-1]
    vector<long long> dp(S + 1); // dp[i]

    for (int i = 0; i < N; ++i) {
        int V, W, K;
        cin >> V >> W >> K;

        if (W == 0) { // Xử lý trường hợp W = 0 (lấy vô hạn nếu V > 0)
            long long total_val = (long long)V * K;
            for (int j = 0; j <= S; ++j) {
                dp[j] = prev_dp[j] + total_val;
            }
            prev_dp = dp;
            continue;
        }

        // Lặp qua từng số dư r
        for (int r = 0; r < W; ++r) {
            deque<int> dq; // Lưu trữ chỉ số x
            
            // Lặp x = 0, 1, 2, ...
            for (int x = 0; (long long)x * W + r <= S; ++x) {
                int j = x * W + r;

                // g(x) = dp[j] - x * V
                long long g_x = prev_dp[j] - (long long)x * V;

                // Bước 1: Duy trì Deque giảm dần
                while (!dq.empty() && 
                       (prev_dp[(long long)dq.back() * W + r] - (long long)dq.back() * V) <= g_x) {
                    dq.pop_back();
                }
                dq.push_back(x);

                // Bước 2: Loại bỏ phần tử ngoài cửa sổ
                if (dq.front() < x - K) {
                    dq.pop_front();
                }

                // Bước 3: Tính dp mới
                // max g(y) = g(dq.front())
                // g(y) = dp[y*W+r] - y*V
                long long max_g = prev_dp[(long long)dq.front() * W + r] - (long long)dq.front() * V;
                dp[j] = max_g + (long long)x * V;
            }
        }
        prev_dp = dp;
    }

    cout << prev_dp[S] << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("snakes.in", "r", stdin); 
    // freopen("snakes.out", "w", stdout);
    int test = 1;
    // cin >> test;
    while (test-- > 0)
    {
        run_test();
    }
}

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