Submission

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

Score: 30

User: NJTYTYTY

Problemset: ช่างไฟ

Language: cpp

Time: 0.062 second

Submitted On: 2025-03-21 08:06:40

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

const int INF = 1e18; // ค่า INF ที่ใช้เปรียบเทียบ

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    
    // กรณีไม่มีจุดซ่อมเลย
    if(N == 0){
        cout << 0 << "\n";
        return 0;
    }
    
    // State เริ่มต้น
    int dp_pos = 0;        // P = 0 (nonnegative)
    bool has_neg = false;  // ยังไม่มี state ที่เป็นลบ
    int dp_neg_hi = 0;     // จะเก็บค่าลบที่ใกล้ 0 มากที่สุด (เมื่อมี)
    int dp_neg_lo = 0;     // จะเก็บค่าลบที่ลึกที่สุด (เมื่อมี)
    
    for (int i = 1; i <= N; i++){
        int a;
        cin >> a;
        
        // ค่า state ใหม่
        int new_dp_pos = -INF; // ต้องการค่าที่ nonnegative มากที่สุด
        bool new_has_neg = false;
        int new_dp_neg_hi = -INF; // สำหรับค่าลบที่ใกล้ 0 (มากที่สุดในกลุ่มลบ)
        int new_dp_neg_lo = INF;  // สำหรับค่าลบที่ลึกที่สุด (น้อยที่สุด)
        
        // ฟังก์ชัน lambda เพื่ออัปเดต state จาก candidate ที่ได้
        auto update = [&](int candidate) {
            if(candidate >= 0) {
                new_dp_pos = max(new_dp_pos, candidate);
            } else {
                if(!new_has_neg) {
                    new_has_neg = true;
                    new_dp_neg_hi = candidate;
                    new_dp_neg_lo = candidate;
                } else {
                    new_dp_neg_hi = max(new_dp_neg_hi, candidate); // ใกล้ 0 มากกว่า
                    new_dp_neg_lo = min(new_dp_neg_lo, candidate);  // ลึกกว่าน้อยกว่า
                }
            }
        };
        
        // ลองจาก state nonnegative (dp_pos)
        if(dp_pos != -INF) {
            int v = dp_pos + a;
            // ทางเลือก 1: ไม่ใช้ absolute
            update(v);
            // ทางเลือก 2: ใช้ absolute (ผลเป็น nonnegative)
            update( (v >= 0 ? v : -v) );
        }
        
        // ลองจาก state ที่เป็นลบ (dp_neg_hi และ dp_neg_lo) หากมี
        if(has_neg) {
            // จาก dp_neg_hi
            {
                int v = dp_neg_hi + a;
                update(v);
                update( (v >= 0 ? v : -v) );
            }
            // จาก dp_neg_lo (ถ้าไม่เท่ากับ dp_neg_hi)
            if(dp_neg_lo != dp_neg_hi) {
                int v = dp_neg_lo + a;
                update(v);
                update( (v >= 0 ? v : -v) );
            }
        }
        
        // อัปเดต state สำหรับขั้นตอนถัดไป
        dp_pos = new_dp_pos;
        has_neg = new_has_neg;
        if(new_has_neg) {
            dp_neg_hi = new_dp_neg_hi;
            dp_neg_lo = new_dp_neg_lo;
        }
    }
    
    // คำตอบคือ dp_pos (state nonnegative ที่ดีที่สุด)
    cout << dp_pos << "\n";
    
    return 0;
}