Submission

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

Score: 30

User: NJTYTYTY

Problemset: ช่างไฟ

Language: cpp

Time: 0.062 second

Submitted On: 2025-03-21 08:03:19

#include <bits/stdc++.h>
#include <algorithm>
#include <climits>
using namespace std;
#define int long long

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

int32_t 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;
}