제출 #1002022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002022		vjudge1	Building Bridges (CEOI17_building)	C++17	100 / 100	65 ms	10580 KiB

building

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

#define fi first
#define se second
#define BIT(n) (1ll << n)
#define GBIT(x, i) ((x >> i) & 1)
#define all(v) v.begin(), v.end()
#define eb emplace_back
#define pb push_back
#define endl '\n'

#define fu(i, l, r) for (int i = (int) (l); i <= (int) (r); i++)
#define fd(i, r, l) for (int i = (int) (r); i >= (int) (l); i--)

typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
typedef unsigned long long ull;
typedef long long ll;
typedef double dl;

const int MAXN = 4e5 + 55;
const int MOD = 1e9 + 7;
const ll oo = 1ll * MOD * MOD;

int n;
int w[MAXN], h[MAXN];

void rf() {
    cin >> n;
    fu(i, 1, n) cin >> h[i];
    fu(i, 1, n) cin >> w[i];
}

struct Line {
    bool t;
    ll m, b;
    dl x;

    bool operator < (const Line &a) const {
        return (t || a.t) ? x < a.x : m > a.m;
    }
};

struct Linecontainer {
    set <Line> cht;
    #define iterLine set <Line> :: iterator

    bool has_prev(iterLine id) {return id != cht.begin();}
    bool has_next(iterLine id) {return id != cht.end() && next(id) != cht.end();}

    dl PointX(iterLine a, iterLine b) {
        return (dl) (a -> b - b -> b) / (b -> m - a -> m);
    }

    bool bad(iterLine id) {
        return has_prev(id) && has_next(id) && PointX(prev(id), next(id)) <= PointX(prev(id), id);
    }

    void calx(iterLine id) {
        Line l = *id;
        if (has_prev(id)) l.x = PointX(prev(id), id);
        else l.x = -oo;
        cht.insert(cht.erase(id), l);
    }

    void add(ll m, ll b) {
        iterLine id = cht.lower_bound({0, m, b, 0});
        if (id != cht.end() && id -> m == m) {
            if (id -> b <= b) return;
            cht.erase(id);
        }

        id = cht.insert({0, m, b, 0}).first;
        if (bad(id)) return void(cht.erase(id));

        while (has_prev(id) && bad(prev(id))) cht.erase(prev(id));
        while (has_next(id) && bad(next(id))) cht.erase(next(id));

        if (has_next(id)) calx(next(id));
        calx(id);
    }

    ll query(ll x) {
        Line l = *prev(cht.upper_bound({1, 0, 0, x}));
        return l.m * x + l.b;
    }
} cht;

ll p[MAXN];

ll _sqr(ll n) {
    return n * n;
}

void solve() {
    fu(i, 1, n) {
        p[i] = p[i - 1] + w[i];
    }

    cht.add(h[1], p[n - 1] - p[1] + _sqr(h[1]));

    ll res = _sqr(h[n] - h[1]) + p[n - 1] - p[1];
//    cout << res << endl;
    fu(i, 2, n - 1) {
        ll cur = _sqr(h[n] - h[i]) - w[i] + _sqr(h[i]) + cht.query(-2 * h[i]);
        res = min(res, cur);
//        cout << res << " " << cur << endl;
        cht.add(h[i], cur -_sqr(h[n] - h[i]) + _sqr(h[i]));
    }
    cout << res << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "prob"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int ntest = 1;
//    cin >> ntest;
    fu(i, 1, ntest) rf(), solve();
}

컴파일 시 표준 에러 (stderr) 메시지

building.cpp: In member function 'll Linecontainer::query(ll)':
building.cpp:85:50: warning: narrowing conversion of 'x' from 'll' {aka 'long long int'} to 'dl' {aka 'double'} [-Wnarrowing]
   85 |         Line l = *prev(cht.upper_bound({1, 0, 0, x}));
      |                                                  ^
building.cpp: In function 'int32_t main()':
building.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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