結果
| 問題 |
No.2026 Yet Another Knapsack Problem
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:16 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,115 bytes |
| コンパイル時間 | 1,120 ms |
| コンパイル使用メモリ | 117,728 KB |
| 実行使用メモリ | 24,580 KB |
| 最終ジャッジ日時 | 2025-05-14 13:04:41 |
| 合計ジャッジ時間 | 14,545 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 TLE * 2 -- * 6 |
ソースコード
#include <iostream>
#include <vector>
#include <deque>
#include <map>
#include <unordered_map> // Using unordered_map for potentially faster average performance
#include <algorithm>
using namespace std;
// Use long long for values and intermediate calculations that might exceed 32-bit integer limits.
using ll = long long;
// Define a large negative number to represent -infinity.
// Using a value far from LLONG_MIN to avoid potential overflow issues during calculations.
// A value around -3e18 should be safe given constraints N <= 2500 and |v_i| <= 10^9.
// Max possible total value can be around N * 10^9 approx 2.5e12. Min possible -2.5e12.
const ll INF = -3e18;
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of item types and maximum total weight/items constraint
cin >> N;
// Store item properties: c[i] = count of items of type i, v[i] = value of item type i
vector<int> c(N + 1);
vector<ll> v(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> c[i] >> v[i];
// The weight of item type i is implicitly i.
}
// DP table: dp[k][w] stores the maximum value achievable using exactly k items with total weight exactly w.
// Initialize all states to -infinity, except the base case.
vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, INF));
dp[0][0] = 0; // Base case: 0 items, 0 weight, 0 value.
// Iterate through each item type i from 1 to N
for (int i = 1; i <= N; ++i) {
// Create a new DP table dp_new based on the state after processing items 1 to i-1 (which is current dp table).
// Updates related to item type 'i' will be stored in dp_new.
// Initializing dp_new as a copy ensures that states not updated by item 'i' retain their previous values.
vector<vector<ll>> dp_new = dp;
// The monotonic queue optimization works on diagonals in the (k, w) state space.
// A diagonal is defined by a constant value D = w - k*i.
// We group states from the previous DP table `dp` based on their diagonal D.
// unordered_map is used for potentially faster average lookup times compared to map.
// It maps diagonal D to another map, which stores {k -> dp[k][w]} for states on that diagonal.
unordered_map<ll, map<int, ll>> states_on_diagonal;
for(int k = 0; k <= N; ++k) {
for(int w = 0; w <= N; ++w) {
// Check if the state (k, w) is reachable (value > -infinity). Use INF/2 check to avoid arithmetic issues near INF.
if (dp[k][w] > INF / 2) {
// Calculate the diagonal identifier D for state (k, w).
ll D = (ll)w - (ll)k * i;
// Store the value dp[k][w] associated with state k on diagonal D.
states_on_diagonal[D][k] = dp[k][w];
}
}
}
// Process each diagonal D found in the previous states.
for (auto const& [D, k_map] : states_on_diagonal) {
// Initialize a deque for the monotonic queue optimization.
// Stores pairs { Y_k', k' }, where Y_k' = dp[k'][k'*i+D] - k'*v[i].
// The queue maintains elements in decreasing order of Y_k', enabling efficient max query.
deque<pair<ll, int>> dq;
// Determine the valid range of k values [k_start, k_end] for this diagonal D.
// A state (k, w) is valid if 0 <= k <= N and 0 <= w <= N.
// Substituting w = k*i + D, we need 0 <= k*i + D <= N.
// Calculate minimum k (k_start).
int k_start = 0;
if (D < 0) {
// Need k*i + D >= 0 => k*i >= -D. Since i >= 1, k >= -D/i.
// We need the smallest integer k satisfying this, which is ceil(-D / i).
// Integer division computes ceil(a/b) for positive a,b as (a + b - 1) / b.
if (i > 0) { // Guarantee i >= 1 from problem statement.
k_start = (int)((-D + i - 1) / i);
}
}
k_start = max(0, k_start); // Ensure k is non-negative.
// Calculate maximum k (k_end).
int k_end;
ll num = (ll)N - D; // Need k*i + D <= N => k*i <= N - D
if (num < 0) {
// If N - D < 0, then k*i <= num < 0. Since k >= 0 and i >= 1, k*i >= 0.
// There is no non-negative k satisfying this condition.
k_end = -1;
} else {
// If N - D >= 0, then k <= (N - D) / i. We need the largest integer k.
// Standard integer division performs floor operation for non-negative numerator.
if (i > 0) { // Guaranteed i >= 1
k_end = (int)(num / i);
} else { // Defensive coding, should not happen.
k_end = N; // If i were 0, k*0 <= num is always true for num >= 0. k restricted by N.
}
k_end = min(N, k_end); // k also cannot exceed N.
}
// Iterate through k in the valid range [k_start, k_end] for this diagonal.
for (int k = k_start; k <= k_end; ++k) {
// Calculate the corresponding weight w for the current k on this diagonal.
ll current_w = (ll)k * i + D;
// Check bounds for w, although the k range calculation should make this redundant.
// if (current_w < 0 || current_w > N) continue;
// Monotonic Queue maintenance: Remove elements from the front that are outside the window.
// The window for state k includes previous states k' such that k - c[i] <= k' <= k.
// We need the values corresponding to k' >= k - c[i].
while (!dq.empty() && dq.front().second < k - c[i]) {
dq.pop_front();
}
// Check if the state (k, current_w) was reachable in the DP table `dp` (before processing item i).
// Access this value using the precomputed `k_map` for the current diagonal D.
ll val_old = INF;
auto it = k_map.find(k);
if (it != k_map.end()) {
val_old = it->second; // Get the stored dp[k][w] value.
}
// If this state (k, current_w) was reachable...
if (val_old > INF / 2) {
// Calculate the value Y_k = dp[k][current_w] - k * v[i] used for queue optimization.
ll Y_k = val_old - (ll)k * v[i];
// Maintain the monotonic property of the queue (decreasing Y values).
// Remove elements from the back with Y value less than or equal to the current Y_k.
while (!dq.empty() && dq.back().first <= Y_k) {
dq.pop_back();
}
// Add the current state's information {Y_k, k} to the back of the queue.
dq.push_back({Y_k, k});
}
// If the queue is not empty, there is a potential maximum value within the window.
if (!dq.empty()) {
// The maximum Y_k' value within the window [k-c[i], k] is at the front of the deque.
ll max_Y_k_prime = dq.front().first;
// Calculate the potential new maximum value for state (k, current_w) using item i optimally.
// This is derived from the formula: dp_new[k][w] = max { Y_k' } + k*v[i].
ll value_with_item_i = max_Y_k_prime + (ll)k * v[i];
// Update the state (k, current_w) in the `dp_new` table.
// Take the maximum of its current value (which might be from `dp` or an earlier update)
// and the newly calculated value `value_with_item_i`.
// Cast current_w back to int for indexing, assuming it remains within [0, N].
dp_new[k][(int)current_w] = max(dp_new[k][(int)current_w], value_with_item_i);
}
}
}
// After processing all diagonals for item type i, update the main DP table `dp`
// by moving the contents of `dp_new`. This is efficient using std::move.
dp = std::move(dp_new);
}
// After processing all item types, find the maximum value for each required number of items k.
for (int k = 1; k <= N; ++k) {
ll max_val = INF;
// The maximum value for exactly k items can occur at any total weight w from 0 to N.
for (int w = 0; w <= N; ++w) {
max_val = max(max_val, dp[k][w]);
}
// Output the maximum value found for exactly k items.
// The problem guarantees that a valid selection exists for each k, so max_val should not be INF.
cout << max_val << "\n";
}
return 0;
}