結果
| 問題 |
No.2026 Yet Another Knapsack Problem
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:10:54 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,425 bytes |
| コンパイル時間 | 1,042 ms |
| コンパイル使用メモリ | 91,684 KB |
| 実行使用メモリ | 16,072 KB |
| 最終ジャッジ日時 | 2025-05-14 13:13:32 |
| 合計ジャッジ時間 | 73,304 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 TLE * 1 -- * 6 |
ソースコード
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
// Define long long for convenience
typedef long long ll;
// Define a very small negative value to represent infinity (unreachable states).
// The maximum possible value sum is approximately N * 10^9 = 2500 * 10^9 = 2.5 * 10^12.
// The minimum possible value sum is approximately N * (-10^9) = -2.5 * 10^12.
// Choose NINF sufficiently small. -3 * 10^18 should be safe.
const ll NINF = -3e18;
int main() {
// Use fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of item types and maximum weight capacity
cin >> N;
// Store counts and values for each item type
vector<int> counts(N + 1);
vector<ll> values(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> counts[i] >> values[i];
}
// Initialize DP table. dp[k][w] stores the maximum value achievable
// using exactly k items with a total weight of exactly w.
vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, NINF));
// Base case: 0 items, 0 weight results in 0 value.
dp[0][0] = 0;
// Iterate through each item type from 1 to N
for (int i = 1; i <= N; ++i) {
int c_i = counts[i]; // Number of items of type i available
ll v_i = values[i]; // Value of one item of type i
int weight = i; // Weight of one item of type i
// Basic check: Item weight must be positive (guaranteed by constraints 1 <= i <= N).
if (weight == 0) continue;
// Create a temporary DP table `next_dp` initialized with the current `dp` state.
// This ensures that updates for item type `i` are based on the results
// from processing items 1 to `i-1`. Using `std::move` later optimizes assignment.
vector<vector<ll>> next_dp = dp;
// Apply the monotonic queue optimization for bounded knapsack.
// Iterate through all possible remainders `r` when weight `w` is divided by `weight`.
for (int r = 0; r < weight; ++r) {
// Calculate the maximum possible quotient `q` such that `q * weight + r <= N`.
int max_q_for_r = (N - r) / weight;
// If `N < r`, then `max_q_for_r` can be negative. No states to process for this `r`.
if (max_q_for_r < 0) continue;
// Calculate the theoretical range of `D = k - q`.
// Minimum D occurs when k=0 and q=max_q_for_r: D = -max_q_for_r.
// Maximum D occurs when k=N and q=0: D = N.
int min_D = -max_q_for_r;
int max_D = N;
int D_range_size = max_D - min_D + 1;
// If the range size is non-positive, skip.
if (D_range_size <= 0) continue;
// Calculate offset to map D values to non-negative indices for vector access.
int offset = -min_D;
// `D_deques` stores one deque for each possible value of D.
// Each deque stores pairs `(q, f(q))`, where `f(q) = dp[k][w] - q * v_i`.
vector<deque<pair<int, ll>>> D_deques(D_range_size);
// Iterate through possible quotients `q` from 0 to `max_q_for_r`.
for (int q = 0; q <= max_q_for_r; ++q) {
int w = q * weight + r; // Current total weight
// Determine the relevant range of D for the current `q`.
// Since `k = D + q`, we must have `0 <= k <= N`, which implies `-q <= D <= N - q`.
// Intersect this with the theoretical range `[min_D, max_D]`.
int current_min_D = max(min_D, -q);
int current_max_D = min(max_D, N - q);
// Iterate through the relevant D values for the current `q`.
for (int D = current_min_D; D <= current_max_D; ++D) {
int k = D + q; // Current number of items
// Get the specific deque for the current D value using the offset.
deque<pair<int, ll>>& dq = D_deques[D + offset];
// Remove elements from the front of the deque whose quotient `q'` is
// outside the sliding window `[q - c_i, q]`. The window size corresponds
// to using 0 up to `c_i` items of type `i`.
while (!dq.empty() && dq.front().first < q - c_i) {
dq.pop_front();
}
// Update `next_dp[k][w]` using the maximum value from the deque.
// The maximum `f(q')` value in the window is at the front of the deque.
if (!dq.empty()) {
ll max_f_q_prime = dq.front().second;
// Check if the value is valid (not derived from an initial NINF state).
// Use NINF / 2 as a threshold to avoid potential issues near NINF boundary.
if (max_f_q_prime > NINF / 2) {
// Calculate the new potential value: `f(q') + q * v_i`
ll new_val = max_f_q_prime + (ll)q * v_i;
// Update `next_dp[k][w]` if this new value is better.
next_dp[k][w] = max(next_dp[k][w], new_val);
}
}
// Consider the value from the DP state *before* processing item `i` (stored in `dp`).
// This value `dp[k][w]` represents the max value using items 1 to `i-1`.
// It's used to maintain the deque for subsequent `q` values.
ll current_dp_val = dp[k][w];
// Check if the state `(k, w)` was reachable before considering item `i`.
if (current_dp_val > NINF / 2) {
// Calculate `f(q) = dp[k][w] - q * v_i`.
ll f_q = current_dp_val - (ll)q * v_i;
// Maintain the monotonic property of the deque: `f(q)` values should be non-increasing.
// Remove elements from the back of the deque that are dominated by the current `f(q)`.
while (!dq.empty() && dq.back().second <= f_q) {
dq.pop_back();
}
// Add the current state information `(q, f(q))` to the back of the deque.
dq.push_back({q, f_q});
}
}
}
}
// After processing item type `i` for all remainders `r`, update the main DP table `dp`.
// `std::move` is used for efficiency to transfer ownership of the data.
dp = std::move(next_dp);
}
// After processing all item types, find and output the answer for each `k` from 1 to N.
for (int k = 1; k <= N; ++k) {
ll max_v = NINF; // Initialize max value for k items to NINF.
// Find the maximum value among all possible weights `w` (0 to N) for fixed `k`.
for (int w = 0; w <= N; ++w) {
max_v = max(max_v, dp[k][w]);
}
// Output the maximum value found for `k` items.
// The problem guarantees that a solution exists for each k, so max_v should be updated from NINF.
cout << max_v << "\n";
}
return 0;
}