Submission #116318

#	Time	Username	Problem	Language	Result	Execution time	Memory
116318		JohnTitor	Building Bridges (CEOI17_building)	C++11	100 / 100	115 ms	14972 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Bridges"
int n, m;
int h[100001];
int x[100001];
int w[100001];
class line{
public:
    ll a, b;
    line(){
        a=0;
        b=1e18;
    }
    line(ll a, ll b){
        this->a=a;
        this->b=b;
    }
    ll at(int x){
        return a*x+b;
    }
};
class linear_segment_tree{
public:
    using pointer=linear_segment_tree*;
    pointer left, right;
    int l, r, m;
    line L;
    linear_segment_tree(int idl, int idr): L(){
        l=x[idl];
        r=x[idr];
        m=x[(idl+idr)/2];
        if(idl!=idr){
            left=new linear_segment_tree(idl, (idl+idr)/2);
            right=new linear_segment_tree((idl+idr)/2+1, idr);
        }
    }
    void update(line A){
        bool gl=A.at(l)<=L.at(l);
        bool gr=A.at(r)<=L.at(r);
        if(gl&&gr) L=A;
        else if(gl||gr){
            left->update(A);
            right->update(A);
        }
    }
    ll get(int u){
        if(l==r) return L.at(u);
        else{
            if(m>=u) return min(left->get(u), L.at(u));
            return min(right->get(u), L.at(u));
        }
    }
};
linear_segment_tree::pointer tree;
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    FOR(i, 1, n) read(h[i]);
    FOR(i, 1, n) read(w[i]);
    FOR(i, 1, n) x[i]=h[i];
    sort(x+1, x+n+1);
    m=unique(x+1, x+n+1)-x-1;
    tree=new linear_segment_tree(1, m);
    tree->update(line(-h[1]*2, ((ll)h[1])*h[1]));
    ll ans=0;
    FOR(i, 2, n){
        ll best=tree->get(h[i]);
        best+=((ll)h[i])*h[i]-w[i];
        tree->update(line(-h[i]*2, best+((ll)h[i])*h[i]));
        if(i==n) ans=best;
    }
    ans+=accumulate(w+2, w+n+1, 0LL);
    writeln(ans);
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40