oj.uz

Submission #964243

# Submission time Handle Problem Language Result Execution time Memory
964243 2024-04-16T13:24:13 Z Pring Building Bridges (CEOI17_building) C++17
100 / 100
 55 ms 14716 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<string, int> psi;

const int MXN = 100005;
const ll INF = 3.9e18;
int n, h[MXN], w[MXN];
int scr[MXN], rnk[MXN], m;
ll dp[MXN], p[MXN];

struct MK {
    ll m, k;
    MK() : m(0), k(0) {}
    MK(ll _m, ll _k) : m(_m), k(_k) {}
    ll operator()(ll x) {
        return m * x + k;
    }
};

struct LCSMG {
    MK val[MXN * 4];
    void init(int n) {
        fill(val, val + n * 4, MK(0, INF));
    }
    void modify(int id, int l, int r, MK L_) {
        MK &L = val[id];
        if (L.m > L_.m) swap(L, L_);
        int mid = (l + r) >> 1;
        if (L(scr[mid]) > L_(scr[mid])) swap(L, L_);
        if (l + 1 == r) return;
        if (L.m < L_.m) modify(id * 2 + 1, l, mid, L_);
        else modify(id * 2 + 2, mid, r, L_);
    }
    ll query(int id, int l, int r, int p) {
        if (l + 1 == r) return val[id](scr[p]);
        int mid = (l + r) >> 1;
        if (p < mid) return min(val[id](scr[p]), query(id * 2 + 1, l, mid, p));
        return min(val[id](scr[p]), query(id * 2 + 2, mid, r, p));
    }
} smg;

void DIST() {
    vector<pii> dist;
    FOR(i, 1, n + 1) dist.push_back(mp(h[i], i));
    sort(dist.begin(), dist.end());
    m = 0;
    for (int i = 0, j = 0; i < n; i = j) {
        while (j < n && dist[i].fs == dist[j].fs) j++;
        scr[m] = dist[i].fs;
        FOR(k, i, j) {
            rnk[dist[k].sc] = m;
        }
        m++;
    }
}

void miku() {
    cin >> n;
    FOR(i, 1, n + 1) cin >> h[i];
    FOR(i, 1, n + 1) cin >> w[i];
    FOR(i, 1, n + 1) p[i] = p[i - 1] + w[i];
    DIST();
    // FOR(i, 0, m) cout << scr[i] << ' ';
    // cout << '\n';
    // FOR(i, 1, n + 1) cout << rnk[i] << ' ';
    // cout << '\n';
    smg.init(m);
    dp[1] = 0;
    smg.modify(0, 0, m, MK(-2 * h[1], (ll) h[1] * h[1] + dp[1] - p[1]));
    FOR(i, 2, n + 1) {
        dp[i] = (ll) h[i] * h[i] + p[i - 1] + smg.query(0, 0, m, rnk[i]);
        smg.modify(0, 0, m, MK(-2 * h[i], (ll) h[i] * h[i] + dp[i] - p[i]));
    }
    cout << dp[n] << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10840 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 13528 KB Output is correct
2 Correct 42 ms 13524 KB Output is correct
3 Correct 43 ms 13588 KB Output is correct
4 Correct 37 ms 13528 KB Output is correct
5 Correct 28 ms 13528 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10840 KB Output is correct
6 Correct 42 ms 13528 KB Output is correct
7 Correct 42 ms 13524 KB Output is correct
8 Correct 43 ms 13588 KB Output is correct
9 Correct 37 ms 13528 KB Output is correct
10 Correct 28 ms 13528 KB Output is correct
11 Correct 55 ms 14716 KB Output is correct
12 Correct 47 ms 14452 KB Output is correct
13 Correct 41 ms 14716 KB Output is correct
14 Correct 49 ms 14548 KB Output is correct
15 Correct 32 ms 14428 KB Output is correct
16 Correct 30 ms 14548 KB Output is correct
17 Correct 23 ms 14552 KB Output is correct
18 Correct 19 ms 14604 KB Output is correct