Submission #1216543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216543		quangminh412	Building Bridges (CEOI17_building)	C++20	100 / 100	42 ms	18388 KiB

building

#include <bits/stdc++.h>
using namespace std;

/*
  Ben Watson
  Handle codeforces : quangminh98

  Mua Code nhu mua Florentino !!
*/

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const ll oo = 0x3f3f3f3f3f3f3f3f;

struct LiChao
{
    struct line
    {
        int a;
        ll b;

        line() : a(0), b(oo) {};
        line(int a, ll b) : a(a), b(b) {};
        ll calc(int x) { return 1ll * a * x + b; }
    };
    vector<line> st;
    int n;

    LiChao(int n) : n(n) { st.resize(n + 1); }

    void add(int l, int r, line seg)
    {
        if (l > r) return;
        int mid = l + r >> 1;
        if (l == r)
        {
            if (st[mid].calc(mid) > seg.calc(mid))
                swap(st[mid], seg);
            return;
        }

        if (seg.calc(mid) < st[mid].calc(mid))
            swap(seg, st[mid]);
        if (seg.a > st[mid].a)
            add(l, mid - 1, seg);
        if (seg.a < st[mid].a)
            add(mid + 1, r, seg);
    }
    void add(int a, ll b) { add(1, n, line(a, b)); }

    ll query(int l, int r, int pos)
    {
        int mid = l + r >> 1;
        ll val = st[mid].calc(pos);
        if (pos == mid) return val;
        if (pos < mid) return min(val, query(l, mid - 1, pos));
        return min(val, query(mid + 1, r, pos));
    }
    ll query(int pos) { return query(1, n, pos); }
};

void solve()
{
    int n; cin >> n;
    int h[n + 1], w[n + 1];
    vector<ll> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        prefix[i] = prefix[i - 1] + w[i];
    }

    LiChao lichao(1e6);
    vector<ll> dp(n + 1, 0);
    lichao.add(-2 * h[1], -prefix[1] + 1ll * h[1] * h[1]);
    for (int i = 2; i <= n; i++)
    {
        dp[i] = prefix[i - 1] + 1ll * h[i] * h[i] + lichao.query(h[i]);
        lichao.add(-2 * h[i], -prefix[i] + 1ll * h[i] * h[i] + dp[i]);
    }

    cout << dp[n] << '\n';
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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