Submission #1125237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125237		yusufhocaoglu	Building Bridges (CEOI17_building)	C++20	100 / 100	111 ms	65396 KiB

building

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl
#define int ll
vi h;int n;
struct Line {
    int a,b;
    Line() {}
    Line(int a,int b) : a(a),b(b) {}
    int operator()(int x) {return a*x+b;}
};
vector<Line> seg;
struct lichao {
    void insert(int i,Line ln,int l,int r) {
        if (l+1==r) {
            if (ln(l)<seg[i](l)) seg[i] = ln;
            return;
        }
        int m = (l+r)/2;
        if (ln.a > seg[i].a) swap(seg[i],ln);
        if (ln(m) < seg[i](m)) {
            //seg has higher slope and higher answer, so seg will always be better in right subtree
            swap(seg[i],ln);
            insert(2*i,ln,l,m);
        } else {
            //seg has higher slope but lower answer, ln should be in this node, and seg should be on the right subtree
            insert(2*i+1,ln,m,r);
        }
    }
    int query(int x,int i,int l,int r) {
        //cout<<"checking "<<x<<" for "<<seg[i].a<<" "<<seg[i].b<<endl;
        if (l+1==r) return seg[i](x);
        int m = (l+r)/2;
        if (x>m) return min(seg[i](x),query(x,2*i+1,m,r));
        return min(seg[i](x),query(x,2*i,l,m)); 
    }
};
int32_t main() {
    cin>>n;
    h = vi(n);
    vi w(n);
    vi p(n+1);
    for (int i = 0;i<n;i++) cin>>h[i];
    for (int i = 0;i<n;i++) {
        cin>>w[i];
        p[i+1] = p[i]+w[i];
    }
    //cout<<"yo nigga"<<endl;
    //prefix is 1-indexed
    int N = 1e6+2;
    seg = vector<Line>(4*N+1,Line(0,1e18));
    lichao lct;
    int ans = 0;
    lct.insert(1,Line(-2*h[0],-p[1]+h[0]*h[0]),0,N);
    for (int i = 1;i<n;i++) {
        ans = lct.query(h[i],1,0,N)+p[i]+h[i]*h[i];
        //cout<<"query for "<<h[i]<<" is "<<ans<<endl;
        lct.insert(1,Line(-2*h[i],ans+h[i]*h[i]-p[i+1]),0,N);
        //cout<<"adding line: "<<-2*h[i]<<"x + "<<ans+h[i]*h[i]-p[i+1]<<endl;
    }
    //cout<<seg[1].a<<" "<<seg[1].b<<endl;
    cout<<ans<<endl;
    return 0;
}

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