Submission #1001475

---

Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    int N;
    long[] A;
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Read();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        int[] chosen = new int[N];
        long[] sum = new long[N];
        int p = 0;
        long t = 0;
        for(int i=2;i<N;i++){
            if(A[i] >= t){
                while(p > 0){
                    t += sum[p-1];
                    t += A[chosen[p-1]];
                    if(A[i] < t){
                        t -= sum[p-1];
                        t -= A[chosen[p-1]];
                        break;
                    }
                    p--;
                }
                sum[p] = t;
                chosen[p] = i;
                p++;
                t = 0; 
            }
            else{
                t += A[i];
            }
        }
        long count = 0;
        count += A[0]-A[1];
        int s = 1;
        for(int i=0;i<p;i++){
            count += s*A[chosen[i]];
            count -= s*sum[i];
            s *= -1;
        }
        sb.Append(count+"\n");
    }
    void Read(){
        N = int.Parse(Console.ReadLine());
        A = new long[N];
        string[] str = Console.ReadLine().Split(' ');
        for(int i=0;i<N-1;i++){
            A[i] = int.Parse(str[i]);
        }
        Console.ReadLine();
        A[N-1] = Int64.Parse(Console.ReadLine());
    }    
}

Submission Info

Judge Result