oj.uz

Submission #877166

# Submission time Handle Problem Language Result Execution time Memory
877166 2023-11-23T02:04:12 Z votranngocvy Building Bridges (CEOI17_building) C++14
0 / 100
 41 ms 4948 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);
    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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2516 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3828 KB Output is correct
2 Correct 41 ms 3924 KB Output is correct
3 Correct 39 ms 3672 KB Output is correct
4 Correct 37 ms 3656 KB Output is correct
5 Incorrect 32 ms 4948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2516 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -