結果
| 問題 |
No.1515 Making Many Multiples
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:42 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,592 bytes |
| コンパイル時間 | 1,230 ms |
| コンパイル使用メモリ | 86,608 KB |
| 実行使用メモリ | 37,096 KB |
| 最終ジャッジ日時 | 2025-05-14 13:08:03 |
| 合計ジャッジ時間 | 4,605 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | AC * 2 TLE * 1 -- * 25 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <vector> // Required for vector
#include <utility> // Required for pair
// Use -1 to indicate an unreachable state, since scores are non-negative (0 or more).
const int INF = -1;
int main() {
// Use fast I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of cards in the deck
int K; // The divisor for checking multiples
long long X, Y; // Initial cards values (can be large)
std::cin >> N >> K >> X >> Y;
// Read the N card values from the deck
std::vector<long long> A(N); // Card values can be large
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
// DP table: dp[x][y] stores the maximum score achieved ending with cards
// having values modulo K equal to x and y, where x <= y.
// Initialize all states to INF (-1), indicating unreachable.
std::vector<std::vector<int>> dp(K, std::vector<int>(K, INF));
// Calculate initial state based on X and Y modulo K.
int x0 = X % K;
int y0 = Y % K;
// Problem statement says X, Y are positive integers, so X, Y >= 1.
// If K=1, X%K and Y%K will be 0.
// If K > 1, X%K and Y%K will be in range [0, K-1].
// No need for negative modulo result handling.
// Ensure x <= y for the state representation (canonical form).
if (x0 > y0) std::swap(x0, y0);
dp[x0][y0] = 0; // The initial score is 0. Mark this state as reachable.
// Keep track of reachable states {x, y} in the current DP table.
// This optimization avoids iterating through all K*K possible states.
std::vector<std::pair<int, int>> reachable_states;
// Add the initial state to the list if it's valid (score >= 0).
if (dp[x0][y0] != INF) {
reachable_states.push_back({x0, y0});
}
// Temporary storage for updates to be applied in the next step.
// Each update is a pair: { {next_state_x, next_state_y}, new_score }.
std::vector<std::pair<std::pair<int, int>, int>> next_updates;
// Reserve some memory to potentially avoid reallocations.
// The maximum number of updates generated from M reachable states is 3*M.
// In worst case M can be up to K*(K+1)/2.
next_updates.reserve(3 * K * (K+1) / 2); // Heuristic reservation size
// Simulate the N steps of the game.
for (int i = 0; i < N; ++i) {
// Get the value of the card drawn at step i, modulo K.
int ai = A[i] % K;
// Problem states A_i are positive integers. Modulo result is non-negative.
next_updates.clear(); // Clear updates from the previous step.
// Iterate through only the states that were reachable after the previous step.
for (const auto& state : reachable_states) {
int x = state.first; // First card value mod K
int y = state.second; // Second card value mod K (x <= y)
int current_score = dp[x][y];
// Defensive check: if state somehow is invalid, skip.
if (current_score == INF) continue;
// Check if the sum of cards in hand (x, y, and newly drawn ai) is a multiple of K.
int score_increment = 0;
// Use long long for the sum calculation to prevent potential overflow before modulo.
// Max sum can be approx 3*10^9 if K=2000, X,Y,A_i near 10^9. Oh wait, x, y, ai are mod K.
// Max sum is (K-1)+(K-1)+(K-1) = 3K-3. Fits in int if 3K < 2^31. K=2000 -> 3K=6000. Fits.
// Let's use long long anyway just to be safe / standard practice.
if (((long long)x + y + ai) % K == 0) {
score_increment = 1; // Score increases by 1 if sum is multiple of K.
}
int new_score = current_score + score_increment; // The score after this step, if transition occurs.
// Calculate the 3 possible next states based on discarding one card.
// Queue these potential updates.
// Option 1: Discard the card corresponding to x mod K. Keep cards y and ai.
int next_y1 = y;
int next_a1 = ai;
// Ensure canonical state representation (smaller value first).
if (next_y1 > next_a1) std::swap(next_y1, next_a1);
next_updates.push_back({{next_y1, next_a1}, new_score});
// Option 2: Discard the card corresponding to y mod K. Keep cards x and ai.
int next_x2 = x;
int next_a2 = ai;
// Ensure canonical state representation.
if (next_x2 > next_a2) std::swap(next_x2, next_a2);
next_updates.push_back({{next_x2, next_a2}, new_score});
// Option 3: Discard the newly drawn card ai. Keep cards x and y.
int next_x3 = x;
int next_y3 = y;
// The state (x, y) is already in canonical form (x <= y).
next_updates.push_back({{next_x3, next_y3}, new_score});
}
// Before applying the updates for the current step, we must reset the DP scores
// for the states that were reachable from the *previous* step. This effectively
// clears the "current" DP state layer to prepare for the "next" layer.
for (const auto& state : reachable_states) {
dp[state.first][state.second] = INF;
}
// Clear the list of reachable states; it will be rebuilt based on the updates.
reachable_states.clear();
// Apply the collected updates.
// Rebuild the `reachable_states` list for the next iteration.
for (const auto& update : next_updates) {
int nx = update.first.first; // Next state x component
int ny = update.first.second; // Next state y component
int score = update.second; // The score achieved reaching this state
// Update the DP table if this path provides a better score,
// or if the state becomes reachable for the first time.
if (dp[nx][ny] == INF || score > dp[nx][ny]) {
// If the state was previously unreachable (INF), add it to the list of
// reachable states for the next iteration.
if (dp[nx][ny] == INF) {
reachable_states.push_back({nx, ny});
}
// Update the DP table with the maximum score found so far for state (nx, ny).
dp[nx][ny] = score;
}
// If score <= dp[nx][ny], this path is not better, so do nothing.
}
// Optional optimization: Deduplicate reachable_states vector.
// This might be beneficial if many updates lead to the same states.
// Can be done using sort + unique, but adds O(M log M) complexity where M is size.
// Decided against it for simplicity and potential overhead. The current loop structure handles duplicates correctly.
}
// After N steps, find the maximum score among all reachable states.
int max_score = 0; // Minimum possible score is 0.
// Check all possible states (x, y) with x <= y in the final DP table.
for (int x = 0; x < K; ++x) {
for (int y = x; y < K; ++y) {
if (dp[x][y] != INF) { // If the state is reachable
max_score = std::max(max_score, dp[x][y]);
}
}
}
// Output the final maximum score.
std::cout << max_score << std::endl;
return 0; // Indicate successful execution.
}