oj.uz

Submission #877178

# Submission time Handle Problem Language Result Execution time Memory
877178 2023-11-23T02:41:29 Z votranngocvy Building Bridges (CEOI17_building) C++14
100 / 100
 49 ms 65628 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
const int N = 1e5 + 5;
const int MAX = 1e6;
const int inf = 0x3f3f3f3f3f3f3f3f;
pii st[4 * MAX + 5];
int h[N],w[N],n;

int f(pii a,int x) {
    return a.fi * x + a.se;
}

void update(int id,int l,int r,pii newLine) {
    int mid = (l + r) / 2;
    if (f(newLine,l) >= f(st[id],l) && f(newLine,r) >= f(st[id],r)) return;
    if (f(newLine,l) <= f(st[id],l) && f(newLine,r) <= f(st[id],r)) {
        st[id] = newLine;
        return;
    }
    if (f(st[id],l) <= f(newLine,l) && f(st[id],mid) <= f(newLine,mid)) {
        update(id * 2 + 1,mid + 1,r,newLine);
        return;
    }
    if (f(st[id],l) >= f(newLine,l) && f(st[id],mid) >= f(newLine,mid)) {
        update(id * 2 + 1,mid + 1,r,st[id]);
        st[id] = newLine;
        return;
    }
    if (f(st[id],r) <= f(newLine,r) && f(st[id],mid + 1) <= f(newLine,mid + 1)) {
        update(id * 2,l,mid,newLine);
        return;
    }
    if (f(st[id],r) >= f(newLine,r) && f(st[id],mid + 1) >= f(newLine,mid + 1)) {
        update(id * 2,l,mid,st[id]);
        st[id] = newLine;
        return;
    }
    update(id * 2,l,mid,newLine);
    update(id * 2 + 1,mid + 1,r,newLine);
}

int get(int id,int l,int r,int x) {
    if (r < x || l > x) return inf;
    int ans = f(st[id],x);
    if (l == r) return ans;
    int mid = (l + r) / 2;
    ans = min(ans,get(id * 2,l,mid,x));
    ans = min(ans,get(id * 2 + 1,mid + 1,r,x));
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for (int i = 1; i <= 4 * MAX; i++) st[i].fi = st[i].se = 1e12 + 10;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        sum += w[i];
    }
    pii tmp = mp(-2 * h[1],h[1] * h[1] - w[1]);
    update(1,0,MAX,tmp);
    for (int i = 2; i < n; i++) {
        int val = get(1,0,MAX,h[i]) + h[i] * h[i] - w[i];
        tmp = mp(-2 * h[i],val + h[i] * h[i]);
        update(1,0,MAX,tmp);
    }
    cout << sum + get(1,0,MAX,h[n]) + h[n] * h[n] - w[n] << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 64316 KB Output is correct
2 Correct 10 ms 64348 KB Output is correct
3 Correct 10 ms 64272 KB Output is correct
4 Correct 11 ms 64348 KB Output is correct
5 Correct 10 ms 64472 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 65392 KB Output is correct
2 Correct 47 ms 65372 KB Output is correct
3 Correct 49 ms 65392 KB Output is correct
4 Correct 46 ms 65244 KB Output is correct
5 Correct 42 ms 65388 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 64316 KB Output is correct
2 Correct 10 ms 64348 KB Output is correct
3 Correct 10 ms 64272 KB Output is correct
4 Correct 11 ms 64348 KB Output is correct
5 Correct 10 ms 64472 KB Output is correct
6 Correct 47 ms 65392 KB Output is correct
7 Correct 47 ms 65372 KB Output is correct
8 Correct 49 ms 65392 KB Output is correct
9 Correct 46 ms 65244 KB Output is correct
10 Correct 42 ms 65388 KB Output is correct
11 Correct 48 ms 65628 KB Output is correct
12 Correct 49 ms 65628 KB Output is correct
13 Correct 41 ms 65624 KB Output is correct
14 Correct 48 ms 65616 KB Output is correct
15 Correct 45 ms 65508 KB Output is correct
16 Correct 42 ms 65364 KB Output is correct
17 Correct 33 ms 65616 KB Output is correct
18 Correct 33 ms 65628 KB Output is correct