oj.uz

Submission #618705

# Submission time Handle Problem Language Result Execution time Memory
618705 2022-08-02T06:49:40 Z nghiass001 Building Bridges (CEOI17_building) C++17
100 / 100
 73 ms 66508 KB 
#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define REPD(i, r, l) for(int i = (r) - 1; i >= (l); --i)
using namespace std;
const long long N = 1e6 + 5, INF = (long long)1e18 + 7;

struct lines {
    long long a, b;
    long long get(long long x) { return a * x + b; }
    lines(long long _a = 0, long long _b = INF) { a = _a; b = _b; }
};

int n;
long long h[N], pre[N], ans[N];
lines it[N * 4];

void Enter() {
    cin >> n;
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) cin >> pre[i], pre[i] += pre[i - 1];
}

void update(lines p, int l = 0, int r = 1e6, int pos = 1) {
    lines q = it[pos];
    int mid = (l + r) / 2;
    if (p.get(l) <= q.get(l) && p.get(r) <= q.get(r)) {
        it[pos] = p;
        return;
    }
    if (p.get(l) >= q.get(l) && p.get(r) >= q.get(r)) {
        return;
    }
    if (p.get(l) <= q.get(l) && p.get(mid) <= q.get(mid)) {
        it[pos] = p;
        update(q, mid + 1, r, pos * 2 + 1);
        return;
    }
    if (p.get(l) >= q.get(l) && p.get(mid) >= q.get(mid)) {
        update(p, mid + 1, r, pos * 2 + 1);
        return;
    }
    if (p.get(mid + 1) <= q.get(mid + 1) && p.get(r) <= q.get(r)) {
        it[pos] = p;
        update(q, l, mid, pos * 2);
        return;
    }
    if (p.get(mid + 1) >= q.get(mid + 1) && p.get(r) >= q.get(r)) {
        update(p, l, mid, pos * 2);
        return;
    }
}

long long query(long long x, int l = 0, int r = 1e6, int pos = 1) {
    long long tmp = it[pos].get(x);
    if (l == r) return tmp;
    int mid = (l + r) / 2;
    if (x <= mid) tmp = min(tmp, query(x, l, mid, pos * 2));
    else tmp = min(tmp, query(x, mid + 1, r, pos * 2 + 1));
    return tmp;
}

void Process() {
    FOR(i, 1, n) {
        if (i != 1) ans[i] = pre[i - 1] + h[i] * h[i] + query(h[i]);
        update(lines(-2 * h[i], ans[i] + h[i] * h[i] - pre[i]));
    }
    cout << ans[n];
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if (fopen("building.inp", "r")) freopen("building.inp", "r", stdin);
    Enter();
    Process();
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:75:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     if (fopen("building.inp", "r")) freopen("building.inp", "r", stdin);
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62932 KB Output is correct
2 Correct 27 ms 62952 KB Output is correct
3 Correct 26 ms 62940 KB Output is correct
4 Correct 27 ms 62952 KB Output is correct
5 Correct 28 ms 62964 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 66292 KB Output is correct
2 Correct 68 ms 66280 KB Output is correct
3 Correct 66 ms 66424 KB Output is correct
4 Correct 62 ms 66148 KB Output is correct
5 Correct 58 ms 66152 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62932 KB Output is correct
2 Correct 27 ms 62952 KB Output is correct
3 Correct 26 ms 62940 KB Output is correct
4 Correct 27 ms 62952 KB Output is correct
5 Correct 28 ms 62964 KB Output is correct
6 Correct 70 ms 66292 KB Output is correct
7 Correct 68 ms 66280 KB Output is correct
8 Correct 66 ms 66424 KB Output is correct
9 Correct 62 ms 66148 KB Output is correct
10 Correct 58 ms 66152 KB Output is correct
11 Correct 73 ms 66508 KB Output is correct
12 Correct 67 ms 66292 KB Output is correct
13 Correct 63 ms 66384 KB Output is correct
14 Correct 73 ms 66380 KB Output is correct
15 Correct 60 ms 66132 KB Output is correct
16 Correct 61 ms 66104 KB Output is correct
17 Correct 49 ms 66256 KB Output is correct
18 Correct 50 ms 66292 KB Output is correct