oj.uz

Submission #964245

# Submission time Handle Problem Language Result Execution time Memory
964245 2024-04-16T13:27:57 Z Pring Building Bridges (CEOI17_building) C++17
100 / 100
 54 ms 13592 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 + 1 == r) {
            if (L(scr[l]) > L_(scr[l])) swap(L, L_);
            return;
        }
        int mid = (l + r) >> 1;
        if (L(scr[mid]) > L_(scr[mid])) swap(L, L_);
        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 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 13528 KB Output is correct
2 Correct 41 ms 13528 KB Output is correct
3 Correct 46 ms 13524 KB Output is correct
4 Correct 37 ms 13592 KB Output is correct
5 Correct 27 ms 13524 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 41 ms 13528 KB Output is correct
7 Correct 41 ms 13528 KB Output is correct
8 Correct 46 ms 13524 KB Output is correct
9 Correct 37 ms 13592 KB Output is correct
10 Correct 27 ms 13524 KB Output is correct
11 Correct 54 ms 13584 KB Output is correct
12 Correct 45 ms 13524 KB Output is correct
13 Correct 42 ms 13568 KB Output is correct
14 Correct 46 ms 13580 KB Output is correct
15 Correct 29 ms 13580 KB Output is correct
16 Correct 29 ms 13528 KB Output is correct
17 Correct 23 ms 13528 KB Output is correct
18 Correct 24 ms 13528 KB Output is correct