Submission #868285

#	Time	Username	Problem	Language	Result	Execution time	Memory
868285		phattruongPO344	Building Bridges (CEOI17_building)	C++14	100 / 100	39 ms	9052 KiB

building

#include<bits/stdc++.h>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define fi   first
#define se   second
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X,class Y>
    void minimize(X &x,const Y &y) {
        if (x>y) x=y;
    }
template<class X,class Y>
    void maximize(X &x,const Y &y) {
        if (x<y) x=y;
    }
template<class T>
    T Abs(const T &x) {
        return (x<0?-x:x);
    }

/* Author: Phat Truong */
const int maxn = 1e5 + 10;
bool line_sort(false);
struct line{
    long long m,b;
    mutable double p;
    line();
    line(long long _m,long long _b,double _p){
        m = _m,b = _b,p = _p;
    }
    bool operator < (const line &x) const{
        if(!line_sort){
            if(m == x.m) return b < x.b;
            return m > x.m;
        }
        return p < x.p;
    }   
};
struct line_container:multiset<line,less<>>{
    const double inf = 1/.0;
    bool intersect(iterator x,iterator y){
        if(y == end()){
            x->p = inf;
            return false;
        }
        if(x -> m == y ->m)
            return true;
        else 
            x->p = (x ->b - y->b)*1.0/(y -> m - x ->m);
        return x ->p >= y->p;
    }
    void add(long long m,long long b){
        iterator z = insert(line(m,b,0));
        iterator y = z++;
        iterator x = y;
        while(intersect(y,z))
            intersect(y, z = erase(z));
        while((x = y) != begin() && intersect(--x,y))
            intersect(x,y = erase(y));
        while((y = x) != begin() && intersect(--x,y))
            intersect(x,y = erase(y)); 
    }
    long long findval(long long x){
        line_sort = true;
        line t = *(lower_bound(line(0,0,x)));
        line_sort = false;
        return (x*t.m + t.b);
    }
};
line_container hull;
long long dp[maxn];
int n;
long long h[maxn];
long long w[maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
   // freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    cin >> n;
    FOR(i,1,n)
        cin >> h[i];
    FOR(i,1,n)
        cin >> w[i];
    FOR(i,1,n)
        w[i] += w[i-1];
    hull.add(-2*h[1],h[1]*h[1] - w[1]);
    dp[1] = 0;
    FOR(i,2,n){
        long long tmp = hull.findval(h[i]);
        dp[i] = tmp + h[i]*h[i] + w[i - 1];
        hull.add(-2*h[i],h[i]*h[i] - w[i] + dp[i]);
    }
    cout << dp[n];
}

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