結果

問題 No.703 ゴミ拾い Easy
ユーザー fgwiebfaoish
提出日時 2020-03-10 22:35:34
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 458 ms / 1,500 ms
コード長 3,859 bytes
コンパイル時間 1,185 ms
コンパイル使用メモリ 114,492 KB
実行使用メモリ 77,384 KB
最終ジャッジ日時 2025-01-02 14:26:56
合計ジャッジ時間 13,293 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
プレゼンテーションモードにする

using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
    const int mod=(int)1e9+7;
    static void Main(){
        Sc sc=new Sc();
        var n=sc.I;
        var a=sc.La;
        var x=sc.La;
        var y=sc.La;
        var dp=new long[n+1];
        Cht cht=new Cht(true);
        for(int i = n-1;i>=0;i--) {
            cht.Add(i,a[i]<<1,-a[i]*a[i]-dp[i+1]);
            var e=cht.Get1(x[i]);
            dp[i]=(-e.Item2)+x[i]*x[i]+y[i]*y[i];
        }
        Console.WriteLine(dp[0]);
    }
}
public class Cht{ 
    private List<Dt> li;
    private bool bo;
    private int k=0;
    private Func<long,long,bool> co;
    public class Dt{
        public int n;
        public long a,b;
        public Dt(int n,long a,long b){this.n=n;this.a=a;this.b=b;}
    }
    public Cht(bool bo){
        this.bo=bo;
        if(bo){co=Ao;}
        else{co=Do;}
        li=new List<Dt>();
    }
    public void Add(int n,long a,long b){
        int m=li.Count-1;
        while(m>0&&co((li[m].a-li[m-1].a)*(b-li[m].b),(li[m].b-li[m-1].b)*(a-li[m].a))){
            li.RemoveAt(m);
            m--;
        }
        li.Add(new Dt(n,a,b));
    }
    public Tuple<int,long> Get1(long n){
        int lb=-1,ub=li.Count-1,mid=0;
        while(lb+1!=ub){
            mid=(ub+lb)>>1;
            if(co(li[mid].a*n+li[mid].b,li[mid+1].a*n+li[mid+1].b)){lb=mid;}
            else{ub=mid;}
        }
        return Tuple.Create(li[ub].n,li[ub].a*n+li[ub].b);
    }
    public Tuple<int,long> Get2(long n){
        while(k<li.Count-1&&co(li[k].a*n+li[k].b,li[k+1].a*n+li[k+1].b)){k++;}
        return Tuple.Create(li[k].n,li[k].a*n+li[k].b);
    }
    private bool Ao(long x,long y){return x<=y;}
    private bool Do(long x,long y){return x>=y;}
}
public class Sc{
    public int I{get{return int.Parse(Console.ReadLine());}}
    public long L{get{return long.Parse(Console.ReadLine());}}
    public double D{get{return double.Parse(Console.ReadLine());}}
    public string S{get{return Console.ReadLine();}}
    public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
    public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
    public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
    public string[] Sa{get{return Console.ReadLine().Split();}}
    public object[] Oa{get{return Console.ReadLine().Split();}}
    public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
    public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
    public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split
        (),int.Parse);}
    public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
    public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
    public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split
        (),long.Parse);}
    public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
    public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
    public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split
        (),double.Parse);}
    public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
    public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
    public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
    public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0