oj.uz

Submission #467831

# Submission time Handle Problem Language Result Execution time Memory
467831 2021-08-24T21:37:10 Z JovanB Building Bridges (CEOI17_building) C++17
100 / 100
 93 ms 10460 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
struct line{
    ll k, n;
} seg[400005];
 
ll h[100005];
ll w[100005];
ll dp[100005];
ll niz[100005];
ll pos[10000005];
 
const int INF1 = 1e9;
const ll INF2 = 1e15;
 
void init(int node, int l, int r){
    seg[node] = {INF1, INF2};
    if(l == r) return;
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
}
 
ll eval(line a, ll b){
    return a.k*b + a.n;
}
 
ll getval(int node, int l, int r, int i){
    //cout << seg[node].k << " " << seg[node].n << " " << i << endl;
    ll tren = eval(seg[node], niz[i]);
    if(l == r) return tren;
    int mid = (l+r)/2;
    if(i <= mid) return min(tren, getval(node*2, l, mid, i));
    else return min(tren, getval(node*2+1, mid+1, r, i));
}
 
void addline(int node, int l, int r, line g){
    if(l == r){
        if(eval(g, niz[l]) <= eval(seg[node], niz[l])) seg[node] = g;
        return;
    }
    int mid = (l+r)/2;
    ll al = eval(g, niz[l]);
    ll bl = eval(seg[node], niz[l]);
    ll ar = eval(g, niz[r]);
    ll br = eval(seg[node], niz[r]);
    ll amid = eval(g, niz[mid]);
    ll bmid = eval(seg[node], niz[mid]);
    if(al <= bl && ar <= br){
        seg[node] = g;
        return;
    }
    if(al <= bl || amid <= bmid) addline(node*2, l, mid, g);
    if(ar <= br || amid <= bmid) addline(node*2+1, mid+1, r, g);
}
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;
 
    int n;
    cin >> n;
    vector <int> hs;
    for(int i=1; i<=n; i++){
        cin >> h[i];
        hs.push_back(h[i]);
    }
    int nn = 0;
    sort(hs.begin(), hs.end());
    for(auto c : hs){
        if(niz[nn] != c || nn == 0) niz[++nn] = c;
    }
    for(int i=1; i<=nn; i++) pos[niz[i]] = i;
    init(1, 1, nn);
    for(int i=1; i<=n; i++){
        cin >> w[i];
        w[i] += w[i-1];
        ll jos = w[i-1] + h[i]*h[i];
        dp[i] = jos+getval(1, 1, nn, pos[h[i]]);
        dp[1] = 0;
        //cout << i << " " << jos << " " << dp[i] << endl;
        line g;
        g.k = -2*h[i];
        g.n = -w[i] + h[i]*h[i] + dp[i];
        //cout << n << " "
        //cout << g.k << " " << g.n << endl;
        addline(1, 1, nn, g);
    }
    //for(int i=1; i<=n; i++) cout << dp[i] << " " << i << endl;
    cout << dp[n];
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 4004 KB Output is correct
2 Correct 83 ms 4560 KB Output is correct
3 Correct 87 ms 4548 KB Output is correct
4 Correct 58 ms 4220 KB Output is correct
5 Correct 74 ms 9756 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 75 ms 4004 KB Output is correct
7 Correct 83 ms 4560 KB Output is correct
8 Correct 87 ms 4548 KB Output is correct
9 Correct 58 ms 4220 KB Output is correct
10 Correct 74 ms 9756 KB Output is correct
11 Correct 76 ms 7744 KB Output is correct
12 Correct 93 ms 7516 KB Output is correct
13 Correct 44 ms 4272 KB Output is correct
14 Correct 83 ms 7628 KB Output is correct
15 Correct 68 ms 10460 KB Output is correct
16 Correct 76 ms 9780 KB Output is correct
17 Correct 24 ms 4324 KB Output is correct
18 Correct 24 ms 4176 KB Output is correct