Submission #1066622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066622		HiepVu217	Building Bridges (CEOI17_building)	C++17	100 / 100	43 ms	9300 KiB

building

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 17, oo = 1e18;
int n, h[N];
long long s[N], ans;
int mode;
struct line
{
    long long a, b;
    mutable long double x;
    int operator < (const line& other) const
    {
        return (!mode ? a < other.a : x < other.x);
    }
};
struct convex: multiset <line>
{
    bool del (iterator u, iterator v)
    {
        if (v == end())
        {
            u -> x = oo;
            return 0;
        }
        if (u -> a == v -> a)
        {
            if (u -> b > v -> b)
            {
                u -> x = oo;
            }
            else
            {
                u -> x = -oo;
            }
        }
        else
        {
            u -> x = (long double)(u -> b - v -> b) / (v -> a - u -> a);
        }
        return (u -> x >= v -> x);
    }
    void add (line l)
    {
        auto w = insert(l);
        auto u = w, v = w; ++w;
        while (del(u, w))
        {
            w = erase(w);
        }
        if (u != begin() && del((--u), v))
        {
            v = erase(v);
            del(u, v);
        }
        while ((v = u) != begin() && del((--u), v))
        {
            v = erase(v);
            del(u, v);
        }
    }
    long long get (long long x)
    {
        if (empty()) return 0;
        mode = 1;
        auto l = *lower_bound({0, 0, x});
        mode = 0;
        return l.a * x + l.b;
    }
} cht;
int main()
{
    ios::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 >> s[i];
        s[i] += s[i - 1];
    }
    cht.add ({2 * h[1], s[1] - 1LL * h[1] * h[1]});
    for (int i = 2; i <= n; ++i)
    {
        ans = -cht.get(h[i]) + 1LL * h[i] * h[i] + s[i - 1];
        cht.add ({h[i] * 2, -ans + s[i] - 1LL * h[i] * h[i]});
    }
    cout << ans;
}

Compilation message (stderr)

building.cpp:3:30: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    3 | const int N = 1e5 + 17, oo = 1e18;
      |                              ^~~~
building.cpp: In member function 'long long int convex::get(long long int)':
building.cpp:65:38: warning: narrowing conversion of 'x' from 'long long int' to 'long double' [-Wnarrowing]
   65 |         auto l = *lower_bound({0, 0, x});
      |                                      ^

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