제출 #615934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
615934		Hanksburger	Building Bridges (CEOI17_building)	C++17	100 / 100	55 ms	7624 KiB

building

#include <bits/stdc++.h>
using namespace std;
long long seg[4000005], dp[100005], h[100005], w[100005];
vector<pair<long long, long long> > v;
void update(long long i, long long l, long long r, long long x)
{
    if (l==r)
    {
        if (v[x].first*l+v[x].second<v[seg[i]].first*l+v[seg[i]].second)
            seg[i]=x;
        return;
    }
    int m=(l+r)/2;
    if (v[x].first*m+v[x].second<v[seg[i]].first*m+v[seg[i]].second)
        swap(x, seg[i]);
    if (v[x].first<v[seg[i]].first)
        update(i*2+1, m+1, r, x);
    else
        update(i*2, l, m, x);
}
long long query(long long i, long long l, long long r, long long x)
{
    if (l==r)
        return v[seg[i]].first*x+v[seg[i]].second;
    long long m=(l+r)/2;
    if (x<=m)
        return min(v[seg[i]].first*x+v[seg[i]].second, query(i*2, l, m, x));
    else
        return min(v[seg[i]].first*x+v[seg[i]].second, query(i*2+1, m+1, r, x));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, sum=0;
    cin >> n;
    for (long long i=1; i<=n; i++)
        cin >> h[i];
    for (long long i=1; i<=n; i++)
    {
        cin >> w[i];
        sum+=w[i];
    }
    dp[1]=h[1]*h[1]-w[1];
    v.push_back({1, 1e16});
    v.push_back({-2*h[1], dp[1]});
    update(1, 0, 1e6, 1);
    for (long long i=2; i<=n; i++)
    {
        dp[i]=query(1, 0, 1e6, h[i])+2*h[i]*h[i]-w[i];
        v.push_back({-2*h[i], dp[i]});
        update(1, 0, 1e6, i);
    }
    cout << dp[n]-h[n]*h[n]+sum;
    return 0;
}

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