結果
| 問題 |
No.1522 Unfairness
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:25 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,708 bytes |
| コンパイル時間 | 1,391 ms |
| コンパイル使用メモリ | 95,348 KB |
| 実行使用メモリ | 32,672 KB |
| 最終ジャッジ日時 | 2025-05-14 13:07:32 |
| 合計ジャッジ時間 | 4,753 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | TLE * 1 -- * 26 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>
using namespace std;
// Using -1 to represent unreachable/invalid states.
// We use long long for O sums as they can potentially exceed 32-bit integer capacity.
// The maximum possible O can be roughly N/2 * max(A_i) = 1500 * 10^6 = 1.5 * 10^9, which fits in 32-bit signed int,
// but sum could exceed 2^31 - 1. Using long long is safer.
const long long INF = -1;
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of elements in the array A
long long M; // Maximum allowed unfairness
cin >> N >> M;
vector<long long> A(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
// Sort the array A in descending order. This helps in the DP state transitions
// as the element A[i] being considered is always the smallest among elements selected so far from A[0...i].
sort(A.rbegin(), A.rend());
// dp0[u] stores the maximum possible sum O achieved using an even number of elements (let's say j),
// such that the calculated unfairness is exactly u. We only store states where u <= M.
// The size is M+1 to cover indices from 0 to M.
vector<long long> dp0(M + 1, INF);
// dp1[u] stores the maximum possible sum O achieved using an odd number of elements (j),
// with calculated alternating sum u. The value 'u' here is the alternating sum B_1 - B_2 + ... + B_j.
// This 'u' can potentially exceed M for odd j states, so we use a map to store these states flexibly.
map<long long, long long> dp1;
// Base case: Before considering any element, we have chosen 0 elements (an even number).
// The sum O is 0, and the unfairness U is 0. This state is valid.
dp0[0] = 0;
// Iterate through each element A[i] of the sorted array (A'_1, A'_2, ..., A'_N)
for (int i = 0; i < N; ++i) {
long long val = A[i]; // The current element value A'_{i+1} being considered
// Create temporary DP states for the next iteration. Initialize with current states.
// This implicitly handles the option of *not* selecting the current element A[i],
// as the previous states are carried over.
vector<long long> next_dp0 = dp0;
map<long long, long long> next_dp1 = dp1;
// --- Process transitions where we *select* the current element A[i] ---
// Transition from states with an even number of elements (dp0) to states with an odd number (next_dp1):
// If we select A[i] and previously had an even number of elements j, the new count j+1 is odd.
// The new element A[i] will be the (j+1)-th element in the sorted list B, which is an odd position.
for (int u = 0; u <= M; ++u) { // Iterate through all possible unfairness values for even counts
if (dp0[u] != INF) { // Check if the state (even count j, unfairness u) is reachable
long long current_O = dp0[u]; // Get the maximum O for this state
// Calculate the new alternating sum u'. Since A[i] is at an odd position (j+1), it adds to the sum.
long long new_u = u + val;
// Calculate the new sum O'. Since A[i] is at an odd position, it contributes to O.
long long new_O = current_O + val;
// Update the state in next_dp1 map for the odd count (j+1).
// If the key new_u doesn't exist or the new O sum is better, update/insert the value.
if (next_dp1.find(new_u) == next_dp1.end() || new_O > next_dp1[new_u]) {
next_dp1[new_u] = new_O;
}
}
}
// Transition from states with an odd number of elements (dp1) to states with an even number (next_dp0):
// If we select A[i] and previously had an odd number of elements j, the new count j+1 is even.
// The new element A[i] will be the (j+1)-th element in the sorted list B, which is an even position.
for (auto const& [u, current_O] : dp1) { // Iterate through all reachable states in dp1 map
// Note: `current_O` retrieved from `dp1` map must be valid (not INF) because we only insert valid states.
// Calculate the new unfairness u'. Since A[i] is at an even position (j+1), it subtracts from the alternating sum.
long long new_u = u - val;
// Calculate the new sum O'. Since A[i] is at an even position, it does not contribute to O.
long long new_O = current_O;
// The alternating sum u' must be non-negative. Based on the property B_p >= B_{p+1}, this should always hold.
// We check for safety.
if (new_u >= 0) {
// Pruning Rule: For states with an even number of elements (stored in dp0), we only care about
// states where the unfairness u' is less than or equal to M.
if (new_u <= M) {
// Update the corresponding state in next_dp0 array if this path yields a better O sum.
if (next_dp0[new_u] == INF || new_O > next_dp0[new_u]) {
next_dp0[new_u] = new_O;
}
}
// If new_u > M, this state is pruned because it violates the constraint for an even number of elements.
}
// If new_u < 0, this indicates an issue, possibly related to numerical precision or logic error,
// but theoretically it shouldn't happen with non-negative A_i and descending sort order.
}
// After considering all transitions for A[i], update the DP states for the next iteration (processing A[i+1])
dp0 = next_dp0;
dp1 = next_dp1;
}
// After iterating through all elements, the final answer is the maximum O found in dp0[u] for any u <= M.
// dp0 contains states with an even number of elements chosen, which corresponds to completed pairs (B_1, B_2), ..., (B_{2k-1}, B_{2k}).
long long max_O = 0; // Initialize max_O to 0. If no valid selection is possible, the answer is 0.
// O represents a sum of elements from A, which are non-negative, so min O is 0.
for (int u = 0; u <= M; ++u) { // Check all possible final unfairness values up to M
if (dp0[u] != INF) { // If a state with unfairness u is reachable
max_O = max(max_O, dp0[u]); // Update max_O if this state gives a larger sum O
}
}
// Output the final maximum O found.
cout << max_O << endl;
return 0;
}