結果

問題 No.703 ゴミ拾い Easy
ユーザー GCC314
提出日時 2018-10-01 21:25:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 46 ms / 1,500 ms
コード長 1,862 bytes
コンパイル時間 731 ms
コンパイル使用メモリ 45,492 KB
実行使用メモリ 13,680 KB
最終ジャッジ日時 2025-01-02 14:02:30
合計ジャッジ時間 3,769 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0