Submission

[PPP][P-SSSS][-S]

Score: 30

User: NJTYTYTY

Problemset: ช่างไฟ

Language: cpp

Time: 0.068 second

Submitted On: 2025-03-21 07:58:04

// #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 <bits/stdc++.h>
#include <algorithm>
#include <climits>
using namespace std;
#define int long long

const int NEG_INF = -1e18;  // สำหรับค่า nonnegative ที่ไม่มีผลลัพธ์ที่ดี
const int POS_INF = 1e18;   // สำหรับค่าเริ่มต้นของ state ลบ (เลือกใช้ค่า INF ในการเปรียบเทียบ)

int N;
int a[1000005];  // จัดเก็บค่าที่ต้องซ่อม

// ฟังก์ชัน top-down recursion
// i         : index ของจุดปัจจุบัน (1-based)
// dp_pos    : ค่าสูงสุดใน state nonnegative ที่มีอยู่ ณ จุดนี้
// dp_neg    : ค่าลบ “ลึกสุด” (ต่ำสุด) ที่มีอยู่ ณ จุดนี้
// has_neg   : flag บอกว่ามี state ลบหรือไม่
int rec(int i, int dp_pos, int dp_neg, bool has_neg) {
    if(i > N) {
        // เมื่อผ่านจุดทั้งหมด ผลลัพธ์ที่ดีที่สุดคือใน state nonnegative
        return dp_pos;
    }
    
    // ค่าใหม่สำหรับ state ของขั้นตอนนี้
    int new_dp_pos = NEG_INF;
    int new_dp_neg = POS_INF;
    bool new_has_neg = false;
    
    // จาก state nonnegative (dp_pos) ที่มีอยู่
    if(dp_pos != NEG_INF) {
        int v = dp_pos + a[i];
        // ทางเลือกที่ 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 ลบ (dp_neg) หากมีอยู่
    if(has_neg) {
        int v = dp_neg + a[i];
        // ทางเลือกที่ 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));
    }
    
    // เรียก recursion สำหรับจุดถัดไป
    return rec(i + 1, new_dp_pos, new_dp_neg, new_has_neg);
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> a[i];
    }
    
    // เริ่มต้น state: P = 0 (nonnegative) และยังไม่มี state ลบ
    int ans = rec(1, 0, 0, false);
    cout << ans << "\n";
    
    return 0;
}