Submission #477398

#	Time	Username	Problem	Language	Result	Execution time	Memory
477398		Tien_Noob	Building Bridges (CEOI17_building)	C++17	100 / 100	134 ms	5712 KiB

building

#define task "BUILDING"

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
constexpr ll Inf = 1e17;

#define sz(x) (int)(x.size())

int n;
ll h[N], w[N], dp[N];

ll A(int x)
{
    return -2 * h[x];
}

ll B(int x)
{
    return dp[x] - w[x] + h[x] * h[x];
}

ll More(int x)
{
    return h[x] * h[x] + w[x - 1];
}

ld inter(int x, int y)
{
    return (ld)1.0 * (B(x) - B(y)) / (A(y) - A(x));
}

struct ConvexHullTrick
{
    vector<int> line;
    vector<ld> point;
    bool Empty;

    ConvexHullTrick()
    {
        Empty = 1;
        point.emplace_back(-Inf);
    }

    void Clear()
    {
        Empty = 1;
        line.clear();
        point.clear();
        point.emplace_back(-Inf);
    }

    void Add(int i)
    {
        while (sz(line) >= 2 || (sz(line) == 1 && A(line[0]) == A(i)))
        {
            if (A(line.back()) != A(i))
            {
                if (inter(i, line.back()) <= inter(i, line[sz(line) - 2]))
                {
                    line.pop_back();
                    point.pop_back();
                }
                else
                    break;
            }
            else
            {
                if (B(line.back()) > B(i))
                {
                    line.pop_back();
                    if (!line.empty())
                        point.pop_back();
                }
                else
                    break;
            }
        }

        Empty = 0;

        if (line.empty() || A(line.back()) != A(i))
        {
            if (!line.empty())
                point.emplace_back(inter(i, line.back()));
            line.emplace_back(i);
        }
    }

    ll Get(int x)
    {
        if (Empty)
            return Inf;
        int j = lower_bound(point.begin(), point.end(), h[x]) - point.begin();
        //cout << line.back() << " " << j - 1 << " " << line[j - 1] << "\n";
        return A(line[j - 1]) * h[x] + B(line[j - 1]) + More(x);
    }
} f[17];

void Read()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i];
        w[i] += w[i - 1];
    }
}

void Update(int x)
{
    int pos = 0;
    vector<int> tmp({x});

    while (pos < 17 && !f[pos].Empty)
    {
        for (auto i : f[pos].line)
            tmp.emplace_back(i);
        f[pos].Clear();
        ++pos;
    }

    sort(tmp.begin(), tmp.end(), [&](const int &x, const int &y)
         { return A(x) > A(y); });

    for (auto i : tmp)
        f[pos].Add(i);
}

void Solve()
{
    Update(1);

    for (int i = 2; i <= n; ++i)
    {
        dp[i] = Inf;
        for (int j = 0; j < 17; ++j)
            if (!f[j].Empty)
            {
                //cout << j << " ";
                dp[i] = min(dp[i], f[j].Get(i));
            }
        Update(i);
        //cout << i << ": " << dp[i] << "\n";
    }

    cout << dp[n];
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}

Compilation message (stderr)

building.cpp: In function 'int32_t main()':
building.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen(task ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         freopen(task ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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