Submission #1174425


Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    public Solve(){}
    int N;
    long[] DPL;
    long[] DPR;
    long[] unuse;
    long[] use;
    long[] sumL;
    long[] sumR;
    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]);
        }
        DPL = new long[N];
        DPR = new long[N];
        {
            sumL = new long[N];
            sumL[0] = T[0];
            for(int i=1;i<N;i++){
                sumL[i] = sumL[i-1] + T[i];
            }
            ConvexHullTrick Con = new ConvexHullTrick(N+1);
            Con.Add(-1,1);
            for(int i=0;i<N;i++){
                DPL[i] = Math.Max(i == 0 ? 0 : DPL[i-1],Con.Query(-i)-sumL[i]+i*(i+1)/2);
                Con.Add(i,DPL[i]+sumL[i]+i*(i-1)/2);
            }
        }
        {
            sumR = new long[N];
            sumR[0] = T[N-1];
            for(int i=1;i<N;i++){
                sumR[i] = sumR[i-1] + T[N-1-i];
            }
            ConvexHullTrick Con = new ConvexHullTrick(N+1);
            Con.Add(-1,1);
            for(int i=0;i<N;i++){
                DPR[N-1-i] = Math.Max(i == 0 ? 0 : DPR[N-i],Con.Query(-i)-sumR[i]+i*(i+1)/2);
                Con.Add(i,DPR[N-1-i]+sumR[i]+i*(i-1)/2);
            }
        }
        unuse = new long[N];
        for(int i=0;i<N;i++){
            unuse[i] = (i == 0 ? 0 : DPL[i-1]) + (i == N-1 ? 0 : DPR[i+1]);
        } 
        use = new long[N];
        for(int i=0;i<N;i++){
            use[i] = -T[i];
        }
        GetUse(0,N-1);
        int M = int.Parse(Console.ReadLine());
        for(int i=0;i<M;i++){
            str = Console.ReadLine().Split(' ');
            int P = int.Parse(str[0])-1;
            long X = int.Parse(str[1]);
            sb.Append(Math.Max(unuse[P],use[P]-X+T[P])+"\n");
        }
    }
    ConvexHullTrick ConL(int l,int r){
        ConvexHullTrick Con = new ConvexHullTrick(r-l+1);
        for(int i=l;i<=r;i++){
            if(i == 0){
                Con.Add(-1,1);
            }
            else{
                Con.Add(i-1,DPL[i-1]+sumL[i-1]+(i-1)*(i-2)/2);
            }
        }
        return Con;
    }
    ConvexHullTrick ConR(int l,int r){
        ConvexHullTrick Con = new ConvexHullTrick(r-l+1);
        for(int i=N-1-r;i<N-l;i++){
            if(i == 0){
                Con.Add(-1,1);
            }
            else{
                Con.Add(i-1,DPR[N-i]+sumR[i-1]+(i-1)*(i-2)/2);
            }
        }
        return Con;
    }
    long UseConL(int i){
        return -sumL[i]+i*(i+1)/2;
    }
    long UseConR(int i){
        return -sumR[N-1-i]+(N-1-i)*(N-i)/2;
    }
    void GetUse(int l,int r){
        int M = (l+r)/2;
        if(l <= M-1){
            GetUse(l,M-1);
        }
        if(M+1 <= r){
            GetUse(M+1,r);
        }
        {
            ConvexHullTrick Con = ConL(l,M);
            long max = -1000000000;
            for(int i=r;i>=M;i--){
                max = Math.Max(max,Con.Query(-i)+UseConL(i)+(i == N-1 ? 0 : DPR[i+1]));
                use[i] = Math.Max(max,use[i]);
            }
        }
        {
            ConvexHullTrick Con = ConR(M,r);
            long max = -1000000000;
            for(int i=l;i<=M;i++){
                max = Math.Max(max,Con.Query(-(N-1-i))+UseConR(i)+(i == 0 ? 0 : DPL[i-1]));
                use[i] = Math.Max(max,use[i]);
            }
        }
    }
}
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

Submission Time
Task F - Contest with Drinks Hard
User leign
Language C# (Mono 4.6.2.0)
Score 0
Code Size 5427 Byte
Status WA
Exec Time 1131 ms
Memory 68628 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
AC × 23
WA × 31
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_high_equaly_01.txt, subtask_1_high_equaly_02.txt, subtask_1_high_equaly_03.txt, subtask_1_high_equaly_04.txt, subtask_1_high_rand_01.txt, subtask_1_high_rand_02.txt, subtask_1_high_rand_03.txt, subtask_1_high_rand_04.txt, subtask_1_killer_01.txt, subtask_1_killer_02.txt, subtask_1_low_equaly_01.txt, subtask_1_low_equaly_02.txt, subtask_1_low_equaly_03.txt, subtask_1_low_equaly_04.txt, subtask_1_low_rand_01.txt, subtask_1_low_rand_02.txt, subtask_1_low_rand_03.txt, subtask_1_low_rand_04.txt, subtask_1_max_high_equaly_01.txt, subtask_1_max_high_equaly_02.txt, subtask_1_max_high_equaly_03.txt, subtask_1_max_high_equaly_04.txt, subtask_1_max_high_rand_01.txt, subtask_1_max_high_rand_02.txt, subtask_1_max_high_rand_03.txt, subtask_1_max_high_rand_04.txt, subtask_1_max_low_equaly_01.txt, subtask_1_max_low_equaly_02.txt, subtask_1_max_low_equaly_03.txt, subtask_1_max_low_equaly_04.txt, subtask_1_max_low_rand_01.txt, subtask_1_max_low_rand_02.txt, subtask_1_max_low_rand_03.txt, subtask_1_max_low_rand_04.txt, subtask_1_max_rand_equaly_01.txt, subtask_1_max_rand_equaly_02.txt, subtask_1_max_rand_equaly_03.txt, subtask_1_max_rand_equaly_04.txt, subtask_1_max_rand_rand_01.txt, subtask_1_max_rand_rand_02.txt, subtask_1_max_rand_rand_03.txt, subtask_1_max_rand_rand_04.txt, subtask_1_min_rand_rand_01.txt, subtask_1_min_rand_rand_02.txt, subtask_1_rand_equaly_01.txt, subtask_1_rand_equaly_02.txt, subtask_1_rand_equaly_03.txt, subtask_1_rand_equaly_04.txt, subtask_1_rand_rand_01.txt, subtask_1_rand_rand_02.txt, subtask_1_rand_rand_03.txt, subtask_1_rand_rand_04.txt
Case Name Status Exec Time Memory
sample_01.txt AC 22 ms 11220 KB
sample_02.txt AC 21 ms 9172 KB
subtask_1_high_equaly_01.txt WA 465 ms 50692 KB
subtask_1_high_equaly_02.txt WA 339 ms 47596 KB
subtask_1_high_equaly_03.txt AC 98 ms 17556 KB
subtask_1_high_equaly_04.txt WA 718 ms 53304 KB
subtask_1_high_rand_01.txt WA 463 ms 50092 KB
subtask_1_high_rand_02.txt WA 336 ms 46576 KB
subtask_1_high_rand_03.txt WA 492 ms 53192 KB
subtask_1_high_rand_04.txt WA 635 ms 49864 KB
subtask_1_killer_01.txt AC 22 ms 13268 KB
subtask_1_killer_02.txt AC 22 ms 11220 KB
subtask_1_low_equaly_01.txt WA 772 ms 50404 KB
subtask_1_low_equaly_02.txt WA 537 ms 58232 KB
subtask_1_low_equaly_03.txt WA 609 ms 53652 KB
subtask_1_low_equaly_04.txt WA 275 ms 48716 KB
subtask_1_low_rand_01.txt WA 594 ms 51232 KB
subtask_1_low_rand_02.txt WA 469 ms 43724 KB
subtask_1_low_rand_03.txt WA 403 ms 49308 KB
subtask_1_low_rand_04.txt WA 762 ms 52576 KB
subtask_1_max_high_equaly_01.txt WA 1114 ms 66480 KB
subtask_1_max_high_equaly_02.txt WA 1122 ms 61936 KB
subtask_1_max_high_equaly_03.txt WA 1123 ms 62880 KB
subtask_1_max_high_equaly_04.txt WA 1117 ms 64532 KB
subtask_1_max_high_rand_01.txt WA 1107 ms 62972 KB
subtask_1_max_high_rand_02.txt WA 1113 ms 64468 KB
subtask_1_max_high_rand_03.txt WA 1109 ms 64208 KB
subtask_1_max_high_rand_04.txt WA 1105 ms 62028 KB
subtask_1_max_low_equaly_01.txt WA 1084 ms 58480 KB
subtask_1_max_low_equaly_02.txt WA 1124 ms 62744 KB
subtask_1_max_low_equaly_03.txt WA 1100 ms 60516 KB
subtask_1_max_low_equaly_04.txt WA 1084 ms 62348 KB
subtask_1_max_low_rand_01.txt WA 1084 ms 60660 KB
subtask_1_max_low_rand_02.txt WA 1131 ms 60576 KB
subtask_1_max_low_rand_03.txt WA 1080 ms 66228 KB
subtask_1_max_low_rand_04.txt WA 1082 ms 64956 KB
subtask_1_max_rand_equaly_01.txt AC 1065 ms 64548 KB
subtask_1_max_rand_equaly_02.txt AC 1059 ms 64532 KB
subtask_1_max_rand_equaly_03.txt AC 1060 ms 62552 KB
subtask_1_max_rand_equaly_04.txt AC 1058 ms 64544 KB
subtask_1_max_rand_rand_01.txt AC 1064 ms 68628 KB
subtask_1_max_rand_rand_02.txt AC 1061 ms 62484 KB
subtask_1_max_rand_rand_03.txt AC 1069 ms 66520 KB
subtask_1_max_rand_rand_04.txt AC 1090 ms 68628 KB
subtask_1_min_rand_rand_01.txt AC 23 ms 11220 KB
subtask_1_min_rand_rand_02.txt AC 22 ms 11220 KB
subtask_1_rand_equaly_01.txt AC 62 ms 20312 KB
subtask_1_rand_equaly_02.txt AC 665 ms 55272 KB
subtask_1_rand_equaly_03.txt AC 293 ms 33504 KB
subtask_1_rand_equaly_04.txt AC 500 ms 48660 KB
subtask_1_rand_rand_01.txt AC 740 ms 62376 KB
subtask_1_rand_rand_02.txt AC 445 ms 41720 KB
subtask_1_rand_rand_03.txt AC 660 ms 59296 KB
subtask_1_rand_rand_04.txt AC 313 ms 27408 KB