Submission #1309864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309864		DangKhoizzzz	Building Bridges (CEOI17_building)	C++17	100 / 100	65 ms	65396 KiB

building

#include <bits/stdc++.h>
#define int long long
#define arr3 array <int , 3>
#define pii pair <int , int>
#define fi first
#define se second
#define BIT(x , k) ((x >> k)&1)
#define MASK(x) (1 << x)

using namespace std;

const int INF = 1e18;
const int maxn = 1e6;

struct line
{
    int a , b;
    int calc(int x) {return a*x + b;}
    line(int aa , int bb) {a = aa; b = bb;}
    line() {a = b = 0;}
};
struct Lichao
{
    vector <line> st;
    Lichao (int n) {st.assign(4*(n+5) , line(0 , INF));}
    void update(int id , int l , int r , line f)
    {
        if(l == r)
        {
            if(st[id].calc(l) > f.calc(l)) st[id] = f;
            return;
        }
        int mid = (l+r)>>1;
        if(f.calc(mid) < st[id].calc(mid)) swap(f , st[id]);
        if(f.a > st[id].a) update(id*2 , l , mid , f);
        else update(id*2+1 , mid+1 , r , f);
    }
    int get(int id , int l , int r , int p)
    {
        int cur = st[id].calc(p);
        if(l == r) return cur;
        int mid = (l+r)>>1;
        if(p <= mid) return min(cur , get(id*2 , l , mid , p));
        return min(cur , get(id*2+1 , mid+1 , r , p));
    }
};
/*
dp[i] = (1 <= j < i) min: dp[j] + pre[i-1] - pre[j] + a[i]^2 + a[j]^2 - 2*a[i]*a[j]
dp[i] = (1 <= j < i) min: -2*a[i]*a[j] + (dp[j] - pre[j] + a[j]^2) + pre[i-1] + a[i]^2
*/
int n , a[maxn] , b[maxn] , pre[maxn];
Lichao lichao(maxn);

void solve()
{
    cin >> n;
    for(int i = 1; i <= n ;i++) cin>> a[i];
    for(int i = 1; i <= n; i++)
    {
        cin >> b[i];
        pre[i] = pre[i-1] + b[i];
    }
    lichao.update(1 , 0 , maxn , line(-2*a[1] , -pre[1] + a[1]*a[1]));
    for(int i = 2; i <= n; i++)
    {
        int res = lichao.get(1 , 0 , maxn , a[i]) + pre[i-1] + a[i]*a[i];
        if(i == n) {cout << res << '\n'; return;}
        lichao.update(1 , 0 , maxn , line(-2*a[i] , res - pre[i]+ a[i]*a[i]));
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

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