結果

問題 No.703 ゴミ拾い Easy
ユーザー GCC314GCC314
提出日時 2018-10-01 21:25:55
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 44 ms / 1,500 ms
コード長 1,862 bytes
コンパイル時間 540 ms
コンパイル使用メモリ 40,948 KB
実行使用メモリ 13,568 KB
最終ジャッジ日時 2024-06-10 18:35:54
合計ジャッジ時間 3,350 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,680 KB
testcase_01 AC 4 ms
7,680 KB
testcase_02 AC 4 ms
7,680 KB
testcase_03 AC 3 ms
7,680 KB
testcase_04 AC 4 ms
7,680 KB
testcase_05 AC 4 ms
7,680 KB
testcase_06 AC 3 ms
7,680 KB
testcase_07 AC 4 ms
7,680 KB
testcase_08 AC 4 ms
7,680 KB
testcase_09 AC 4 ms
7,680 KB
testcase_10 AC 4 ms
7,680 KB
testcase_11 AC 4 ms
7,680 KB
testcase_12 AC 5 ms
7,680 KB
testcase_13 AC 4 ms
7,680 KB
testcase_14 AC 5 ms
7,680 KB
testcase_15 AC 4 ms
7,680 KB
testcase_16 AC 4 ms
7,680 KB
testcase_17 AC 4 ms
7,680 KB
testcase_18 AC 3 ms
7,680 KB
testcase_19 AC 4 ms
7,680 KB
testcase_20 AC 3 ms
7,680 KB
testcase_21 AC 5 ms
7,680 KB
testcase_22 AC 4 ms
7,680 KB
testcase_23 AC 5 ms
7,680 KB
testcase_24 AC 44 ms
13,568 KB
testcase_25 AC 44 ms
13,568 KB
testcase_26 AC 44 ms
13,548 KB
testcase_27 AC 42 ms
13,568 KB
testcase_28 AC 42 ms
13,568 KB
testcase_29 AC 42 ms
13,568 KB
testcase_30 AC 41 ms
13,568 KB
testcase_31 AC 42 ms
13,568 KB
testcase_32 AC 42 ms
13,548 KB
testcase_33 AC 42 ms
13,568 KB
testcase_34 AC 38 ms
13,568 KB
testcase_35 AC 38 ms
13,568 KB
testcase_36 AC 37 ms
13,532 KB
testcase_37 AC 38 ms
13,568 KB
testcase_38 AC 36 ms
13,568 KB
testcase_39 AC 37 ms
13,568 KB
testcase_40 AC 38 ms
13,568 KB
testcase_41 AC 38 ms
13,504 KB
testcase_42 AC 39 ms
13,560 KB
testcase_43 AC 38 ms
13,568 KB
testcase_44 AC 4 ms
7,680 KB
testcase_45 AC 4 ms
7,680 KB
testcase_46 AC 41 ms
13,568 KB
testcase_47 AC 42 ms
13,564 KB
testcase_48 AC 4 ms
7,680 KB
testcase_49 AC 4 ms
7,680 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
typedef long long LL;
const int N = 300300,LIM = 100000;
const LL inf = 1e18;
inline int getint()
{
    int r = 0,s = 0;char c = getchar();for(;!isdigit(c);c = getchar()) s |= c == '-';
    for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? -r : r;
}
struct line
{
    LL k,b;
    line(){k = 0,b = inf;}
    line(LL k_,LL b_){k = k_;b = b_;}
    inline LL v(LL x){return k * x + b;}
    inline friend double X(const line &a,const line &b){return 1.0 * (a.b - b.b) / (b.k - a.k);}
};
struct SegmentTree
{
    line val[(LIM + 10) << 2];
    inline void insert(int k,int l,int r,line w)
    {
        // printf("i %d %d %d %lld %lld\n",k,l,r,w.k,w.b);
        if(val[k].b == inf) {val[k] = w;return;}
        line w2 = val[k];
        if(w.v(l) <= w2.v(l)) std::swap(w,w2);
        if(w.v(r) >= w2.v(r)) {val[k] = w2;return;}
        if(l == r) return;
        double x = X(w,w2);
        int mid = (l + r) >> 1;
        if(x <= 1.0 * mid) {val[k] = w;insert(k << 1,l,mid,w2);}
        else {val[k] = w2;insert(k << 1 | 1,mid + 1,r,w);}
    }
    inline LL query(int k,int l,int r,int p)
    {
        LL re = val[k].v(p);
        if(l == r) return re;
        int mid = (l + r) >> 1;
        re = std::min(re,p <= mid ? query(k << 1,l,mid,p) : query(k << 1 | 1,mid + 1,r,p));
        return re;
    }
}SGT;
int a[N],x[N],y[N];
LL f[N];
int n;
int main()
{
    int n = getint();
    for(int i = 1;i <= n;i++) a[i] = getint();
    for(int i = 1;i <= n;i++) x[i] = getint();
    for(int i = 1;i <= n;i++) y[i] = getint();
    for(int i = 1;i <= n;i++)
    {
        SGT.insert(1,0,LIM,line(-2LL * x[i],1LL * x[i] * x[i] + 1LL * y[i] * y[i] + f[i - 1]));
        f[i] = 1LL * a[i] * a[i] + SGT.query(1,0,LIM,a[i]);
    }
    printf("%lld\n",f[n]);
    return 0;
}
0