Submission #1282638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282638		quanw267	Building Bridges (CEOI17_building)	C++17	100 / 100	66 ms	66184 KiB

building

#include<bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(0), cin.tie(0);

using namespace std;
const long long N = 1e5, M = 1e6, INF = 1e16;
long long w[N+5];
long long h[N+5];
long long pre[N+5];
long long f[N+5];

struct Line {
    long long a, b;
    Line(long long _a = 0, long long _b = INF) : a(_a), b(_b) {}

    long long siu(long long x) const { return a*x + b; }
};

Line st[4*M+5];

void update(long long id, long long l, long long r, Line k){
    long long mid = (l+r)/2;
    if(k.siu(mid) < st[id].siu(mid)) swap(k, st[id]);
    if(l+1 == r) return;

    if(k.siu(l) < st[id].siu(l)) update(id*2,l, mid, k);
    else update(id*2+1, mid, r, k);
}

long long get(long long id, long long l, long long r, long long x){
    long long res = st[id].siu(x);
    if(l+1 == r) return res;
    long long mid = (l+r)/2;
    if(x < mid) return min(res, get(id*2,l,mid,x));
    else return min(res, get(id*2+1,mid,r,x));
}

main(){
    fast
    long long n;
    cin >> n;
    for(long long i=1; i<=n;  i++) cin >> h[i];
    for(long long i=1 ;i<=n; i++){
    cin >> w[i];
    pre[i] = pre[i-1] + w[i];
    }
    f[1] = 0;
    update(1, 0, M+1, {-2*h[1], f[1]+h[1]*h[1]-pre[1]});
    for(long long i=2; i<=n ;i++){
        f[i] = get(1, 0, M+1, h[i]) + h[i]*h[i] + pre[i-1];
        update(1, 0, M+1, {-2*h[i], f[i] + h[i]*h[i] - pre[i]});
    }
    cout << f[n];
    return 0;
}

Compilation message (stderr)

building.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~

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