oj.uz

Submission #541115

# Submission time Handle Problem Language Result Execution time Memory
541115 2022-03-22T09:03:05 Z Vladth11 Building Bridges (CEOI17_building) C++14
100 / 100
 74 ms 66444 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 1000001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 16;

ll h[NMAX], w[NMAX];
ll dp[NMAX];

struct functie{
    ll a, b;
    ll f(ll x){
        if(b == INF) /// Asta e notatia ca functia nu exista
            return INF;
        return a + b * x;
    }
}lichao[NMAX * 4];

void baga(int node, int st, int dr, functie x){
    if(st == dr){
        if(lichao[node].f(st) > x.f(st))
            swap(lichao[node], x);
        return;
    }
    int mid = (st + dr) / 2;
    ll ls = lichao[node].f(st);
    ll lm = lichao[node].f(mid);
    ll xs = x.f(st);
    ll xm = x.f(mid);
    if(xm < lm){
        swap(lichao[node], x);
        if(xs > ls)
            baga(node * 2, st, mid, x);
        else
            baga(node * 2 + 1, mid + 1, dr, x);
    }else{
        if(xs > ls)
            baga(node * 2 + 1, mid + 1, dr, x);
        else
            baga(node * 2, st, mid, x);
    }
}

ll query(int node, int st, int dr, int poz){
    if(st == dr){
        return lichao[node].f(poz);
    }
    int mid = (st + dr) / 2;
    ll minim = lichao[node].f(poz);
    if(poz <= mid){
        minim = min(minim, query(node * 2, st, mid, poz));
    }else{
        minim = min(minim, query(node * 2 + 1, mid + 1, dr, poz));
    }
    return minim;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, i;
    cin >> n;
    for(i = 1; i < 4 * NMAX; i++)
        lichao[i].b = INF;
    for(i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(i = 1; i <= n; i++){
        cin >> w[i];
        w[i] += w[i - 1];
    }
    for(i = 1; i <= n; i++){
        ll sum = h[i] * h[i] + w[i - 1];
        ll minim = query(1, 0, NMAX, h[i]);
        if(i == 1){
            dp[i] = 0;
        }else{
            dp[i] = sum + minim;
        }
        baga(1, 0, NMAX, {h[i] * h[i] - w[i] + dp[i], -2 * h[i]});
    }
    cout << dp[n];
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62924 KB Output is correct
2 Correct 26 ms 62860 KB Output is correct
3 Correct 24 ms 62924 KB Output is correct
4 Correct 25 ms 62980 KB Output is correct
5 Correct 25 ms 62916 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 66288 KB Output is correct
2 Correct 62 ms 66312 KB Output is correct
3 Correct 69 ms 66328 KB Output is correct
4 Correct 62 ms 66132 KB Output is correct
5 Correct 59 ms 66136 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62924 KB Output is correct
2 Correct 26 ms 62860 KB Output is correct
3 Correct 24 ms 62924 KB Output is correct
4 Correct 25 ms 62980 KB Output is correct
5 Correct 25 ms 62916 KB Output is correct
6 Correct 64 ms 66288 KB Output is correct
7 Correct 62 ms 66312 KB Output is correct
8 Correct 69 ms 66328 KB Output is correct
9 Correct 62 ms 66132 KB Output is correct
10 Correct 59 ms 66136 KB Output is correct
11 Correct 74 ms 66424 KB Output is correct
12 Correct 66 ms 66188 KB Output is correct
13 Correct 62 ms 66444 KB Output is correct
14 Correct 73 ms 66364 KB Output is correct
15 Correct 61 ms 66064 KB Output is correct
16 Correct 62 ms 66116 KB Output is correct
17 Correct 49 ms 66304 KB Output is correct
18 Correct 52 ms 66284 KB Output is correct