結果

問題 No.703 ゴミ拾い Easy
ユーザー GCC314GCC314
提出日時 2018-10-01 21:25:07
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,860 bytes
コンパイル時間 441 ms
コンパイル使用メモリ 40,724 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-20 14:21:49
合計ジャッジ時間 5,496 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 WA -
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 AC 1 ms
6,940 KB
testcase_45 AC 1 ms
6,944 KB
testcase_46 RE -
testcase_47 RE -
testcase_48 WA -
testcase_49 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
typedef long long LL;
const int N = 30030,LIM = 10000;
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