Submission #561200

#	Time	Username	Problem	Language	Result	Execution time	Memory
561200		fatemetmhr	Building Bridges (CEOI17_building)	C++17	30 / 100	3083 ms	4832 KiB

building

#include <bits/stdc++.h>

using namespace std;

typedef long long    ll;
typedef pair<ll, ll> pll;

#define pb      push_back
#define all(x)  x.begin(), x.end()
#define fi      first
#define se      second
#define mp      make_pair

const int maxn5 = 1e5 + 10;
const int ssq   = 320;
const ll  inf   = 1e18;


struct _cht{
    int pt;
    pair <ll, pll> a[maxn5]; // {st, {const, shib}}
    void clear(){
        pt = 0;
    }

    ll inter(pll a, pll b){ // az koja b akidan behtar hast?
        if(a.se == b.se)
            return (a.fi > b.fi ? inf : -inf);
        return (a.fi - b.fi) / (b.se - a.se) + ((a.fi - b.fi) % (b.se - a.se) > 0);
    }

    void add(pll x){
        while(pt && inter(a[pt].se, x) <= a[pt].fi)
            pt--;
        a[pt] = mp(-inf, x);
        if(pt)
            a[pt].fi = inter(a[pt].se, x);
        pt++;
    }

    ll get_max(ll x){
        int id = upper_bound(a, a + pt, mp(x, mp(inf, inf))) - a - 1;
        return a[id].se.fi + a[id].se.se * x;
    }

} cht;

ll h[maxn5], w[maxn5];
ll dp[maxn5];
set <pair<ll, int>> av;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n; cin >> n;
    for(int i = 0; i < n; i++)
        cin >> h[i];
    for(int i = 0; i < n; i++){
        cin >> w[i];
        if(i)
            w[i] += w[i - 1];
    }

    cht.clear();

    for(int j = 1; j < n; j++){
        dp[j] = inf;
        for(int k = 0; k < j; k++) 
            dp[j] = min(dp[j], dp[k] + w[j - 1] - w[k] + h[k] * h[k] + h[j] * h[j] - 2 * h[j] * h[k]);

    }

    cout << dp[n - 1] << endl;
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40