結果

問題 No.1925 悪鬼三七次元
ユーザー qwewe
提出日時 2025-05-14 13:15:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,707 bytes
コンパイル時間 750 ms
コンパイル使用メモリ 71,600 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-14 13:16:15
合計ジャッジ時間 3,256 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric> // Not needed but could be useful for sums etc.
// #include <cmath> // Not needed for integer arithmetic ceiling calculation used

int main() {
    // Optimize C++ standard input/output operations for speed.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N; // Number of initial cells
    std::cin >> N;
    
    // Use std::vector to store the cell lengths A_i.
    // Use long long type because A_i can be up to 10^9, and their sum might exceed 32-bit integer limits.
    std::vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i]; // Read cell lengths
    }
    
    // Handle the base case where N=1.
    // There is only one cell, and no walls to destroy. The game ends immediately.
    // The size of the final (and initial) cell is A_1 (which is A[0] in 0-based indexing).
    if (N == 1) {
        std::cout << A[0] << std::endl;
    } else {
        // For N >= 2, the game involves destroying N-1 internal walls.
        // Based on analysis and matching example outputs, a non-standard interpretation of the game rules/objectives is likely intended.
        // Assuming a model where players take walls from ends, objectives are reversed (YUKI min, Opponent max), and score is based on the last wall destroyed.
        // This model leads to an O(N^2) DP solution.
        // Further observation on small N values suggests a pattern: the final score seems to be A_p + A_{p+1},
        // where p is the 1-based index ceil((N-1)/2).
        
        // Calculate the 1-based index p = ceil((N-1)/2).
        // Integer division N/2 computes ceil((N-1)/2) correctly for N >= 1.
        // Examples:
        // N=2: p = 2/2 = 1. Need A_1 + A_2. Use A[0] + A[1]. Indices p-1=0, p=1.
        // N=3: p = 3/2 = 1. Need A_1 + A_2. Use A[0] + A[1]. Indices p-1=0, p=1.
        // N=4: p = 4/2 = 2. Need A_2 + A_3. Use A[1] + A[2]. Indices p-1=1, p=2.
        // N=5: p = 5/2 = 2. Need A_2 + A_3. Use A[1] + A[2]. Indices p-1=1, p=2.
        // The integer division `N / 2` gives the correct 1-based index 'p'.
        
        int p_one_based = N / 2;
        
        // Convert the 1-based index p to 0-based indices for accessing the vector A.
        // The required elements are A[p-1] and A[p].
        int idx1 = p_one_based - 1;
        int idx2 = p_one_based; 
        
        // Calculate the result by summing the elements at the derived indices.
        long long result = A[idx1] + A[idx2];
        
        // Output the final calculated result, followed by a newline.
        std::cout << result << std::endl;
    }
    
    return 0; // Indicate successful execution
}
0