結果

問題 No.3103 Butterfly Effect
ユーザー qwewe
提出日時 2025-05-14 13:14:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,940 bytes
コンパイル時間 1,004 ms
コンパイル使用メモリ 97,432 KB
実行使用メモリ 15,264 KB
最終ジャッジ日時 2025-05-14 13:15:02
合計ジャッジ時間 13,599 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 7 TLE * 1 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath> // For abs()

using namespace std;

// Define long long type for potentially large sums
typedef long long ll;

// Define a constant for negative infinity. Use a value smaller than any possible sum.
// Max sum could be N * max(|A_i|) = 200000 * 10^9 = 2 * 10^14.
// So -2 * 10^18 should be safe.
const ll INF = -2e18; 

int main() {
    // Optimize input/output operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    // Handle edge case N=0 although problem statement says N >= 1
    if (N == 0) {
        cout << 0 << endl;
        return 0;
    }

    // Read input array A
    vector<ll> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Initialize DP table. dp[i] will store the maximum absolute sum for the prefix A[0...i-1].
    // dp table size is N+1. dp[0] = 0 for empty prefix.
    vector<ll> dp(N + 1, 0); 

    // Monotonic stack storing indices (1-based). The values at these indices are decreasing.
    vector<int> stack_indices; 
    // Corresponding values A[p_m - 1] for indices p_m in stack_indices.
    vector<ll> stack_values;  

    // Iterate through the array elements to compute DP values
    for (int i = 1; i <= N; ++i) {
        // Current element A[i-1] (since A is 0-indexed and i is 1-based loop counter)
        ll current_val = A[i - 1];
        
        // Maintain the monotonic stack property (decreasing values).
        // Pop elements from stack whose values are less than or equal to current_val.
        // The effective start index for range calculations related to A[i-1] is determined by the last element NOT popped.
        // This p_prev_idx_for_new_elem logic is implicitly handled by the DP calculation loop below.
        while (!stack_indices.empty() && stack_values.back() <= current_val) {
            stack_indices.pop_back();
            stack_values.pop_back();
        }

        // Push current element's index (1-based) and value onto stack
        stack_indices.push_back(i);
        stack_values.push_back(current_val);

        // Calculate DP[i] using the current stack state.
        // Initialize max DP value for current state 'i' to negative infinity.
        ll max_dp_for_i = INF; 

        // Tracks p_{m-1} (start boundary index, exclusive) for the range of 'j'.
        // It's the index of the previous element on stack (or 0 if it's the first element).
        int current_p_prev_idx = 0; 
        
        // Iterate through stack elements m=1 to k
        // k_idx corresponds to the index in the stack vector (0-based)
        for (int k_idx = 0; k_idx < stack_indices.size(); ++k_idx) {
            // Get the index p_m (1-based) and value V_m = A[p_m - 1] from stack
            int p_m = stack_indices[k_idx]; 
            ll V_m = stack_values[k_idx];  
            // Calculate absolute value of V_m
            ll abs_V_m = abs(V_m);

            // Calculate H_m = max_{j=current_p_prev_idx+1}^{p_m} { DP[j-1] - |V_m|*j }
            // This inner loop is the bottleneck, making the overall complexity O(N^2).
            // An optimized solution would replace this loop with a fast query on a data structure.
            ll max_term_for_Hm = INF;
            for (int j = current_p_prev_idx + 1; j <= p_m; ++j) {
                 // Compute the term DP[j-1] - |V_m| * j
                 // Ensure 1LL is used for multiplication to avoid overflow if j is large
                 ll term = dp[j - 1] - abs_V_m * (1LL * j);
                 // Update the maximum term found so far
                 max_term_for_Hm = max(max_term_for_Hm, term);
            }
            
            ll H_m = max_term_for_Hm;

            // If H_m was successfully computed (i.e., the range for j was not empty and calculation happened)
            if (H_m != INF) {
                 // Compute the candidate value for DP[i] using this stack element's contribution
                 // current_dp_candidate = |V_m| * (i + 1) + H_m
                 // Use 1LL for multiplication involving 'i' to ensure 64-bit arithmetic
                 ll current_dp_candidate = abs_V_m * (1LL * i + 1) + H_m;
                 // Update the maximum DP value found for state 'i'
                 max_dp_for_i = max(max_dp_for_i, current_dp_candidate);
            }

            // Update the boundary index for the next iteration.
            // The next range for 'j' starts after the current p_m.
            current_p_prev_idx = p_m;
        }
        
        // Assign the computed maximum value to dp[i].
        // If max_dp_for_i remained INF, it means something went wrong or N=0 case wasn't handled?
        // Based on analysis, this should not happen for N>=1.
        dp[i] = max_dp_for_i;
    }

    // The final answer is the DP value for the entire array, which is dp[N].
    cout << dp[N] << endl;

    return 0;
}
0