Submission #541115

#	Time	Username	Problem	Language	Result	Execution time	Memory
541115		Vladth11	Building Bridges (CEOI17_building)	C++14	100 / 100	74 ms	66444 KiB

building

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40