Submission #1066089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066089		vjudge1	Building Bridges (CEOI17_building)	C++17	30 / 100	3064 ms	3668 KiB

building

//    Tiger II H my beloved    //
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 16;
long long n, dp[N], h[N], w[N], k, sum = 0;
struct line
{
    long long a,b;
};
line l[N], s[N];
double e[N];
bool ok (long long i)
{
    if (l[i].a == s[k].a)
    {
        return true;
    }
    if (k==1)
    {
        return false;
    }
    double x1, x2;
    x1 = 1.0 * (l[i].b - s[k-1].b) / (s[k-1].a - l[i].a);
    x2 = 1.0 * (s[k].b - s[k-1].b) / (s[k-1].a - s[k].a);
    return (x1 <= x2);
}
void sub1()
{
    dp[1] = -w[1];
    for (int i = 2; i <= n; i ++)
    {
        dp[i] = 1e18;
        for (int j = 1; j < i; j ++)
        {
            dp[i] = min (dp[i], dp[j] + (h[i] - h[j]) * (h[i] - h[j]) - w[i]);
        }
    }
    for (int i = 1; i <= n; i ++)
    {
        sum += w[i];
    }
    cout<<sum + dp[n];
}
int main () {
    ios_base::sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);

    cin>>n;
    for (int i = 1; i <= n; i ++)
    {
        cin>>h[i];
    }
    for (int i = 1; i <= n; i ++)
    {
        cin>>w[i];
    }
    sub1();
    return 0;
    dp[1] = -w[1];
    l[1].a = -2 * h[1];
    l[1].b = h[1] * h[1] + dp[1];
    s[1] = l[1];
    e[1] = 1.0e18;
    k = 1;
    for (int i = 2; i <= n; i ++)
    {
        long long j = lower_bound (e + 1, e + k + 1, h[i]) - e;
        dp[i] = s[j].a * h[i] + s[j].b + h[i] * h[i] - w[i];

        l[i].a = -2 * h[i];
        l[i].b = h[i] * h[i] + dp[i];
        if (l[i].a == s[k].a and l[i].b >= s[k].b)
        {
            continue;
        }
        while (k > 0 and ok(i) == true)
        {
            k--;
        }
        k++;
        s[k] = l[i];
        e[k - 1] = 1.0 * (s[k].b - s[k - 1].b) / (s[k - 1].a - s[k].a);
        e[k] = 1.0e18;
    }
    for (int i = 1; i <= n; i ++)
    {
        sum += w[i];
    }
    for (int i = 1; i <= n; i ++)
    {
        cout<<dp[i]<<" ";
    }

    return 0;
}

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