Submission

Compilation Error

Score: 0

User: NJTYTYTY

Problemset: ช่างไฟ

Language: cpp

Time: 0.000 second

Submitted On: 2025-03-21 08:00:07

// #include <iostream>
// #include <vector>
// #include <algorithm>
// using namespace std;
// typedef long long ll;

// int main(){
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
    
//     int T;
//     cin >> T;
//     while(T--){
//         int N;
//         cin >> N;
//         vector<ll> L(N);
//         for (int i = 0; i < N; i++){
//             cin >> L[i];
//         }
        
//         // เราจะ binary search หาค่า D ที่มากที่สุด (D = T - 1)
//         // โดยค่า D ต้องเป็น non-negative integer
//         ll lo = 0, hi = 1e10; // กำหนดขอบเขต hi ให้สูงพอ
//         ll best = 0;
//         while(lo <= hi){
//             ll mid = lo + (hi - lo) / 2;
//             __int128 req = 0; // ใช้ __int128 เพื่อป้องกัน overflow
//             for (int i = 0; i < N; i++){
//                 if(mid > L[i] - 1){
//                     req += (mid - (L[i] - 1));
//                     if(req > mid) break; // ไม่ต้องคิดต่อถ้าเกิน
//                 }
//             }
//             if(req <= mid){
//                 best = mid;
//                 lo = mid + 1;
//             } else {
//                 hi = mid - 1;
//             }
//         }
        
//         // ผลลัพธ์ที่ต้องการคือ T = D + 1
//         cout << best + 1 << "\n";
//     }
    
//     return 0;
// }

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
#define int long long

// เรากำหนด INF ให้มีค่ามากพอ สมมุติใช้ 1e18
const int INF = 1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    
    // กรณีไม่มีจุดซ่อมเลย
    if(N == 0){
        cout << 0 << "\n";
        return 0;
    }
    
    // เริ่มต้น P = 0 ซึ่งเป็น nonnegative state
    int dp_pos = 0;
    // dp_neg จะเก็บค่าลบที่ “ลึกสุด” ถ้ามี state ลบในขั้นตอนนั้น
    int dp_neg = 0; // ค่าเริ่มต้นไม่สำคัญ เพราะยังไม่มี state ลบ
    bool has_neg = false;
    
    for (int i = 1; i <= N; i++){
        int a;
        cin >> a;
        
        // เริ่มค่าสำหรับขั้นตอนใหม่
        int new_dp_pos = -INF; // เราต้องการค่าสูงสุด nonnegative
        int new_dp_neg = INF;  // สำหรับ state ลบ เราต้องการค่าน้อยที่สุด (deepest negative)
        bool new_has_neg = false;
        
        // ลองมาจาก state nonnegative (dp_pos)
        if(dp_pos != -INF){ // dp_pos มีอยู่เสมอ
            int v = dp_pos + a;
            // ทางเลือกที่ 1: ไม่ใช้ absolute
            if(v >= 0){
                new_dp_pos = max(new_dp_pos, v);
            } else {
                new_dp_neg = min(new_dp_neg, v);
                new_has_neg = true;
            }
            // ทางเลือกที่ 2: ใช้ absolute จะได้ nonnegative
            new_dp_pos = max(new_dp_pos, (v >= 0 ? v : -v));
        }
        
        // ลองมาจาก state negative (dp_neg) ถ้ามี
        if(has_neg){
            int v = dp_neg + a;
            // ทางเลือกที่ 1: ไม่ใช้ absolute
            if(v >= 0){
                new_dp_pos = max(new_dp_pos, v);
            } else {
                new_dp_neg = min(new_dp_neg, v);
                new_has_neg = true;
            }
            // ทางเลือกที่ 2: ใช้ absolute
            new_dp_pos = max(new_dp_pos, (v >= 0 ? v : -v));
        }
        
        // อัปเดต state สำหรับขั้นตอนนี้
        dp_pos = new_dp_pos;
        if(new_has_neg){
            dp_neg = new_dp_neg;
            has_neg = true;
        } else {
            has_neg = false;
        }
    }
    
    // ผลลัพธ์ที่ดีที่สุดจะอยู่ใน dp_pos เพราะเป็น nonnegative
    cout << dp_pos << "\n";
    
    return 0;
}