oj.uz

Submission #557240

# Submission time Handle Problem Language Result Execution time Memory
557240 2022-05-05T00:30:33 Z CyberSleeper Building Bridges (CEOI17_building) C++17
100 / 100
 72 ms 66476 KB 
#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ull         unsigned long long
#define pll         pair<ll, ll>
#define pii         pair<ll, ll>
#define ld          long double
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
#define sqr(x)      (x)*(x)
using namespace std;

const ll MX=100005, MOD=1000000007, BLOCK=327, INF=2e9+7;
const ll INFF=1000000000000000007;
const ld ERR=1e-6, pi=3.14159265358979323846;

ll N, H[MX], W[MX], DP[MX], sumW;

struct Seg{

    #define mi      (le+ri)/2
    #define idxl    (idx*2+1)
    #define idxr    (idx*2+2)

    ll x;
    struct line{
        ll m=0, c=INFF;
    }ST[40*MX], now;

    ll f(line g, ll xx){
        return g.m*xx+g.c;
    }
    void upd(ll idx, ll le, ll ri){
        bool lef=(f(now, le)<f(ST[idx], le)), mid=(f(now, mi)<f(ST[idx], mi));
        if(mid)
            swap(now, ST[idx]);
        if(le+1==ri)
            return;
        if(lef!=mid)
            upd(idxl, le, mi);
        else
            upd(idxr, mi,  ri);
    }
    ll que(ll idx, ll le, ll ri){
        if(le+1==ri)
            return f(ST[idx], x);
        if(x<=mi)
            return min(f(ST[idx], x), que(idxl, le, mi));
        return min(f(ST[idx], x), que(idxr, mi, ri));
    }

    void update(ll mm, ll cc){
        now.m=mm, now.c=cc;
        upd(0, 0, 1000000);
    }
    ll query(ll xx){
        x=xx;
        return que(0, 0, 1000000);
    }

}LCT;

int main(){
    fastio;
    cin >> N;
    for(ll i=1; i<=N; i++)
        cin >> H[i];
    for(ll i=1; i<=N; i++){
        cin >> W[i];
        sumW+=W[i];
    }
    DP[1]=sumW-W[1];
    LCT.update(-2ll*H[1], sqr(H[1])+DP[1]);
    for(ll i=2; i<=N; i++){
        DP[i]=sqr(H[i])-W[i]+LCT.query(H[i]);
        LCT.update(-2ll*H[i], sqr(H[i])+DP[i]);
    }
    cout << DP[N] << nl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62928 KB Output is correct
2 Correct 24 ms 62872 KB Output is correct
3 Correct 28 ms 62928 KB Output is correct
4 Correct 28 ms 62944 KB Output is correct
5 Correct 27 ms 62956 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 66256 KB Output is correct
2 Correct 64 ms 66268 KB Output is correct
3 Correct 63 ms 66180 KB Output is correct
4 Correct 60 ms 66180 KB Output is correct
5 Correct 59 ms 66148 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62928 KB Output is correct
2 Correct 24 ms 62872 KB Output is correct
3 Correct 28 ms 62928 KB Output is correct
4 Correct 28 ms 62944 KB Output is correct
5 Correct 27 ms 62956 KB Output is correct
6 Correct 62 ms 66256 KB Output is correct
7 Correct 64 ms 66268 KB Output is correct
8 Correct 63 ms 66180 KB Output is correct
9 Correct 60 ms 66180 KB Output is correct
10 Correct 59 ms 66148 KB Output is correct
11 Correct 72 ms 66404 KB Output is correct
12 Correct 72 ms 66276 KB Output is correct
13 Correct 66 ms 66332 KB Output is correct
14 Correct 69 ms 66476 KB Output is correct
15 Correct 58 ms 66032 KB Output is correct
16 Correct 60 ms 66104 KB Output is correct
17 Correct 53 ms 66264 KB Output is correct
18 Correct 50 ms 66284 KB Output is correct