Submission #1174460

---

Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    public Solve(){}
    int N;
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        N = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        long[] T = new long[N];
        for(int i=0;i<N;i++){
            T[i] = int.Parse(str[i]);
        }
        int M = int.Parse(Console.ReadLine());
        for(int j=0;j<M;j++){
            str = Console.ReadLine().Split(' ');
            long originalT = T[int.Parse(str[0])-1];
            T[int.Parse(str[0])-1] = int.Parse(str[1]);
            long[] DP = new long[N];
            long[] sum = new long[N];
            sum[0] = T[0];
            for(int i=1;i<N;i++){
                sum[i] = sum[i-1] + T[i];
            }
            ConvexHullTrick Con = new ConvexHullTrick(N+1);
            Con.Add(-1,1);
            for(int i=0;i<N;i++){
                DP[i] = Math.Max(i == 0 ? 0 : DP[i-1],Con.Query(-i)-sum[i]+i*(i+1)/2);
                Con.Add(i,DP[i]+sum[i]+i*(i-1)/2);
            }
            sb.Append(DP[N-1]+"\n");
            T[int.Parse(str[0])-1] = originalT;
        }
    }
}

struct ConvexHullTrick{
    long[] A;
    long[] B;
    //C[i]はi番目の点に適用するのがi+1番目の点に適用するよりも大きくなる最大のx 単調増加になる
    long[] C;
    int p;
    int find;
    public ConvexHullTrick(int N){
        A = new long[N];
        B = new long[N];
        C = new long[N];
        p = 0;
        find = 0;
    }
    //aは単調増加でないといけない
    public void Add(long a,long b){
        if(p == 0){
            A[0] = a;
            B[0] = b;;
            p++;
        }
        else{
            for(int i=p;i>0;i--){
                long X = Compare(A[i-1],B[i-1],a,b);
                if(i == 1 || X > C[i-2]){
                    C[i-1] = X;
                    A[i] = a;
                    B[i] = b;
                    p = i+1;
                    break;
                }
            }
        }
    }
    //1つはAddしていないといけない
    public long Query(long x){
        return Calc(x,findMax(x));
    }
    int findMax(long x){
        find = Math.Min(find,p-1);
        while(find < p-1 && C[find] < x){
            find++;
        }
        while(find > 0 && C[find-1] >= x){
            find--;
        }
        return find;
    }
    long Calc(long x,int i){
        return A[i]*x + B[i];
    }
    //(a1,b1)に適用する方が(a2,b2)に適用するより大きくなる最大のx
    long Compare(long a1,long b1,long a2,long b2){
        return (b1-b2-1)/(a2-a1) - ((b1-b2-1)%(a2-a1) < 0 ? 1 : 0);
    }
}

Submission Info

Judge Result