oj.uz

Submission #263258

# Submission time Handle Problem Language Result Execution time Memory
263258 2020-08-13T14:45:35 Z alexandra_udristoiu Building Bridges (CEOI17_building) C++14
100 / 100
 174 ms 9208 KB 
#include<iostream>
#include<algorithm>
#define DIM 100005
#define x first
#define y second
#define ll long long
using namespace std;
int n, i, m;
int h[DIM], w[DIM], a[DIM];
pair<ll, ll> aint[4 * DIM], p[DIM];
long long sum, d[DIM];
long long calc(pair<ll, ll> p, int i){
    return p.x * 1LL * i + p.y;
}
void build(int nod, int st, int dr){
    aint[nod] = p[1];
    if(st != dr){
        int mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
    }
}
void update(int nod, int st, int dr, pair<ll, ll> p){
    int mid = (st + dr) / 2;
    if( calc(aint[nod], a[mid]) > calc(p, a[mid]) ){
        swap(aint[nod], p);
    }
    if(st != dr){
        if( calc(aint[nod], a[st]) < calc(p, a[st]) ){
            update(2 * nod + 1, mid + 1, dr, p);
        }
        else{
            update(2 * nod, st, mid, p);
        }
    }
}
long long query(int nod, int st, int dr, int p){
    if(st == dr){
        return calc(aint[nod], p);
    }
    else{
        int mid = (st + dr) / 2;
        long long x;
        if(p <= a[mid]){
            x = query(2 * nod, st, mid, p);
        }
        else{
            x = query(2 * nod + 1, mid + 1, dr, p);
        }
        return min(x, calc(aint[nod], p) );
    }
}
int main(){
    cin>> n;
    for(i = 1; i <= n; i++){
        cin>> h[i];
        a[i] = h[i];
    }
    sort(a + 1, a + n + 1);
    for(i = 1; i <= n; i++){
        cin>> w[i];
        m = max(m, h[i]);
        sum += w[i];
        p[i].y = h[i] * 1LL * h[i] - w[i];
        p[i].x = -2 * h[i];
    }
    build(1, 1, n);
    for(i = 2; i <= n; i++){
        d[i] = query(1, 1, n, h[i]) - w[i] + h[i] * 1LL * h[i];
        p[i].y = d[i] + h[i] * 1LL * h[i];
        update(1, 1, n, p[i]);
    }
    cout<< d[n] + sum;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 7928 KB Output is correct
2 Correct 173 ms 8952 KB Output is correct
3 Correct 158 ms 9208 KB Output is correct
4 Correct 145 ms 8936 KB Output is correct
5 Correct 125 ms 8824 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 156 ms 7928 KB Output is correct
7 Correct 173 ms 8952 KB Output is correct
8 Correct 158 ms 9208 KB Output is correct
9 Correct 145 ms 8936 KB Output is correct
10 Correct 125 ms 8824 KB Output is correct
11 Correct 174 ms 9100 KB Output is correct
12 Correct 159 ms 9080 KB Output is correct
13 Correct 153 ms 9080 KB Output is correct
14 Correct 170 ms 9164 KB Output is correct
15 Correct 118 ms 8824 KB Output is correct
16 Correct 121 ms 8824 KB Output is correct
17 Correct 123 ms 9040 KB Output is correct
18 Correct 124 ms 9084 KB Output is correct