結果
| 問題 |
No.1977 Extracting at Constant Intervals
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:16:32 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,983 bytes |
| コンパイル時間 | 1,129 ms |
| コンパイル使用メモリ | 92,876 KB |
| 実行使用メモリ | 817,440 KB |
| 最終ジャッジ日時 | 2025-05-14 13:17:55 |
| 合計ジャッジ時間 | 5,313 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | MLE * 2 -- * 29 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map> // Using map for cache as N can be large
// Function to compute Greatest Common Divisor (GCD)
long long gcd(long long a, long long b) {
// Ensure non-negative inputs for standard GCD definition
// Absolute values are needed if inputs could be negative, but N, L are positive per constraints.
// If a=0 or b=0, standard definitions apply: gcd(a, 0) = |a|.
// Constraints: N>=1, L>=1. So a, b >= 1.
while (b) {
a %= b;
std::swap(a, b);
}
return a;
}
// Structure to hold precomputed data for a starting index modulo N
// This data depends only on the remainder of (i-1) modulo N.
struct PrecomputedData {
std::vector<long long> period_values; // Stores A[p_k] for one period
long long period_sum = 0; // Sum of values in one period
std::vector<long long> prefix_sums; // Prefix sums within a period
bool computed = false; // Flag to check if data has been computed for this residue class
};
int main() {
// Fast I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
long long N; // Number of elements in A
long long M; // Number of times A is concatenated
long long L; // Interval length
std::cin >> N >> M >> L;
std::vector<long long> A(N); // Input array A
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
// Calculate the total length of sequence B. N*M can be up to 10^5 * 10^9 = 10^14. Fits in long long.
long long total_len = N * M;
// Precompute GCD of N and L. Constraints ensure N >= 1, L >= 1.
long long common_divisor = gcd(N, L);
// Calculate the length of the period P. P = N / gcd(N, L).
// Since N >= 1 and common_divisor >= 1, P >= 1.
long long P = N / common_divisor;
// Cache to store precomputed data for each residue class modulo N.
// Using map keyed by residue r_idx = (i-1) % N. Size is at most N.
std::map<long long, PrecomputedData> cache;
// Initialize max_C to a sufficiently small value. The minimum possible sum could be total_len * min(A_i).
// min(A_i) >= -10^4. total_len <= 10^14. Min sum >= -10^18.
// Use -4e18 as a safe lower bound.
long long max_C = -4e18;
bool first_val_set = false; // Flag to track if max_C has been properly initialized
// Determine the range of indices `i` to check.
// A full check requires iterating i from 1 to L. This is too slow if L is large.
// It is known that for functions like g(k) = floor(k/P)*S + Pref(k mod P), the maximum over an interval [k_min, k_max]
// is often found near the boundaries of the interval, specifically within P elements from k_min and k_max.
// Correspondingly for C_i = g(K_i+1), K_i decreases as i increases.
// The maximum C_i is likely found for i near 1 (giving large K_i) or i near L (giving small K_i).
// This suggests checking i values in [1, N] and [L-N+1, L] might be sufficient. This is a heuristic.
// Let's use this heuristic as it's common in competitive programming problems with similar structure.
std::vector<long long> indices_to_check;
if (L <= 2 * N) { // If L is small (e.g., comparable to N), check all indices from 1 to L.
for (long long i = 1; i <= L; ++i) {
indices_to_check.push_back(i);
}
} else { // If L is large, check the first N indices and the last N indices.
for (long long i = 1; i <= N; ++i) {
indices_to_check.push_back(i);
}
// Check indices from L-N+1 up to L. Ensure indices are at least 1.
for (long long i = std::max(1LL, L - N + 1); i <= L; ++i) {
indices_to_check.push_back(i);
}
// Sort and remove duplicates if ranges overlap (unlikely needed if L > 2N, but safe).
std::sort(indices_to_check.begin(), indices_to_check.end());
indices_to_check.erase(std::unique(indices_to_check.begin(), indices_to_check.end()), indices_to_check.end());
}
// If N=0, A is empty, total_len is 0. The sums C_i will be 0. Max is 0.
if (N == 0) {
max_C = 0;
first_val_set = true;
} else { // Standard case N >= 1
for (long long i : indices_to_check) {
// Calculate residue index `r_idx` = (i-1) mod N. This is 0-based index corresponding to A.
long long r_idx = (i - 1) % N;
// Check if data for this residue class `r_idx` is already computed and cached.
if (cache.find(r_idx) == cache.end()) { // If not in cache map, compute it. Note: map default constructs if accessed. Check first.
PrecomputedData data; // Create new data structure instance
data.period_values.reserve(P); // Reserve space for efficiency
data.prefix_sums.reserve(P + 1);
data.prefix_sums.push_back(0); // Prefix sum of 0 elements is 0
long long current_idx = r_idx; // Start walk from index r_idx
for(int k=0; k<P; ++k) {
// Bounds check for A access, although current_idx guaranteed to be in [0, N-1] by modulo arithmetic
long long val = A[current_idx];
data.period_values.push_back(val);
data.period_sum += val;
data.prefix_sums.push_back(data.period_sum); // Store prefix sum up to k-th element
// Move to the next index in the sequence: (current_idx + L) mod N
current_idx = (current_idx + L) % N;
// Ensure positive result for modulo if intermediate potentially negative (not possible here as N,L>0)
// if (current_idx < 0) current_idx += N;
}
data.computed = true; // Mark as computed
cache[r_idx] = data; // Store computed data in cache map
}
// Retrieve precomputed data from cache
const PrecomputedData& data = cache[r_idx];
// Calculate K_i = floor((total_len - i) / L)
long long K_i = -1; // Initialize to represent invalid/empty sum range
if (total_len >= i && L > 0) { // Check if i is within total length and L is positive
K_i = (total_len - i) / L;
} else if (total_len < i) { // If i is beyond the sequence B length
K_i = -1; // Represents 0 terms
} // L=0 case is excluded by constraints L >= 1.
// Number of terms in the sum for C_i is K_i + 1
long long num_terms = K_i + 1;
if (num_terms <= 0) { // If there are no terms in the sum for C_i
long long current_C = 0; // The sum over an empty set is 0.
// Update max_C if this is the first value or if 0 is greater than current max.
if (!first_val_set || current_C > max_C) {
max_C = current_C;
first_val_set = true; // Mark that max_C is now initialized with a valid value
}
continue; // Move to the next index i
}
// Calculate number of full periods and remaining terms
long long num_full_periods = num_terms / P;
long long remaining_terms = num_terms % P;
// Calculate the sum C_i using precomputed values
long long current_C = num_full_periods * data.period_sum; // Sum from full periods
// Add sum from remaining terms using prefix sums. Check bounds.
if (remaining_terms >= 0 && remaining_terms < data.prefix_sums.size()) {
current_C += data.prefix_sums[remaining_terms];
} else {
// This path indicates an error in logic or indexing, should not happen with P>=1.
// E.g. remaining_terms could be P, which is index P+1. prefix_sums has size P+1 (indices 0..P).
// Index `remaining_terms` corresponds to sum of first `remaining_terms` elements.
// This is correctly stored at index `remaining_terms`.
}
// Update the overall maximum value found so far
if (!first_val_set || current_C > max_C) {
max_C = current_C;
first_val_set = true; // Mark that max_C holds a valid computed value
}
}
} // End loop over indices_to_check
// If N >= 1 and M >= 1, sequence B is non-empty. L >= 1. At least one C_i will have terms.
// So first_val_set should be true unless N=0 case handled above.
// If after all checks max_C remains at its initial very small value, it indicates an issue.
// But based on constraints, at least one C_i sum will be computed.
std::cout << max_C << std::endl; // Output the final maximum value
return 0;
}