oj.uz

Submission #1002022

# Submission time Handle Problem Language Result Execution time Memory
1002022 2024-06-19T09:20:24 Z vjudge1 Building Bridges (CEOI17_building) C++17
100 / 100
 65 ms 10580 KB 
#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();
}

Compilation message

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3112 KB Output is correct
2 Correct 49 ms 3148 KB Output is correct
3 Correct 49 ms 3136 KB Output is correct
4 Correct 65 ms 2788 KB Output is correct
5 Correct 59 ms 4444 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 49 ms 3112 KB Output is correct
7 Correct 49 ms 3148 KB Output is correct
8 Correct 49 ms 3136 KB Output is correct
9 Correct 65 ms 2788 KB Output is correct
10 Correct 59 ms 4444 KB Output is correct
11 Correct 52 ms 3044 KB Output is correct
12 Correct 50 ms 3128 KB Output is correct
13 Correct 32 ms 3164 KB Output is correct
14 Correct 48 ms 3280 KB Output is correct
15 Correct 57 ms 10580 KB Output is correct
16 Correct 45 ms 4688 KB Output is correct
17 Correct 16 ms 2904 KB Output is correct
18 Correct 12 ms 2904 KB Output is correct