oj.uz

Submission #503735

# Submission time Handle Problem Language Result Execution time Memory
503735 2022-01-08T18:50:29 Z fvogel499 Building Bridges (CEOI17_building) C++17
100 / 100
 51 ms 36664 KB 
/*
 * File created on 01/08/2022 at 19:13:29.
 * Link to problem: 
 * Description: 
 * Time complexity: O()
 * Space complexity: O()
 * Status: ---
 * Copyright: Ⓒ 2022 Francois Vogel
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

#define pii pair<int, int>
#define f first
#define s second

#define vi vector<int>
#define all(x) x.begin(), x.end()
#define size(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear

#define int ll
#define ll long long
#define ld long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int p2 = 1<<20;
const int inf = 1e18;

struct LiChao {
    LiChao() {
        t = new pii [p2*2];
        for (int i = 0; i < p2*2; i++) t[i] = pii(0, inf);
    }
    void update(pii v, int x = 1, int b = 0, int e = p2-1) {
        int m = (b+e)/2;
        if (t[x].f*m+t[x].s > v.f*m+v.s) swap(t[x], v);
        if (b < e) {
            if (v.f > t[x].f) {
                update(v, x*2, b, m);
            }
            else {
                update(v, x*2+1, m+1, e);
            }
        }
    }
    int get(int x) {
        int r = inf;
        for (int i = p2+x; i; i /= 2) r = min(r, t[i].f*x+t[i].s);
        return r;
    }
    pii* t;
};

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

    int n;
    cin >> n;
    int b [n];
    for (int i = 0; i < n; i++) cin >> b[i];
    int w [n];
    for (int i = 0; i < n; i++) cin >> w[i];
    LiChao lc = LiChao();
    int dp [n];
    for (int i = n-1; i >= 0; i--) {
        dp[i] = lc.get(b[i]);
        if (i == n-1) dp[i] = 0;
        dp[i] += 2*b[i]*b[i];
        dp[i] -= w[i];
        lc.update(pii(-2*b[i], dp[i]));
    }
    int res = dp[0]-b[0]*b[0]-b[n-1]*b[n-1];
    for (int i : w) res += i;
    cout << res;

    cout.flush();
    int d = 0;
    d++;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33068 KB Output is correct
2 Correct 17 ms 33124 KB Output is correct
3 Correct 17 ms 33076 KB Output is correct
4 Correct 17 ms 33168 KB Output is correct
5 Correct 19 ms 33092 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 36388 KB Output is correct
2 Correct 47 ms 36396 KB Output is correct
3 Correct 47 ms 36512 KB Output is correct
4 Correct 48 ms 36512 KB Output is correct
5 Correct 43 ms 36416 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33068 KB Output is correct
2 Correct 17 ms 33124 KB Output is correct
3 Correct 17 ms 33076 KB Output is correct
4 Correct 17 ms 33168 KB Output is correct
5 Correct 19 ms 33092 KB Output is correct
6 Correct 46 ms 36388 KB Output is correct
7 Correct 47 ms 36396 KB Output is correct
8 Correct 47 ms 36512 KB Output is correct
9 Correct 48 ms 36512 KB Output is correct
10 Correct 43 ms 36416 KB Output is correct
11 Correct 51 ms 36664 KB Output is correct
12 Correct 51 ms 36400 KB Output is correct
13 Correct 50 ms 36548 KB Output is correct
14 Correct 50 ms 36636 KB Output is correct
15 Correct 41 ms 36268 KB Output is correct
16 Correct 44 ms 36420 KB Output is correct
17 Correct 40 ms 36548 KB Output is correct
18 Correct 49 ms 36532 KB Output is correct