oj.uz

답안 #561214

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
561214 2022-05-12T13:16:25 Z fatemetmhr Building Bridges (CEOI17_building) C++17
100 / 100
 1301 ms 12440 KB 
#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){
        //cout << "hey a very nice x " << x.fi << ' ' << x.se << endl;
        while(pt && inter(a[pt - 1].se, x) <= a[pt - 1].fi)
            pt--;
        a[pt] = mp(-inf, x);
        if(pt)
            a[pt].fi = inter(a[pt - 1].se, x);
        //cout << "with final pos " << pt << ' ' << a[pt].fi << endl;
        pt++;
    }

    ll get_max(ll x){
        int id = upper_bound(a, a + pt, mp(x, mp(inf, inf))) - a - 1;
        //cout << "asking for " << x << ' ' << pt << ' ' << id << endl;
        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();
    cht.add({w[0] - h[0] * h[0], 2 * h[0]});
    av.insert({h[0], 0});

    for(int i = 0; i < n; i += ssq){
        for(int j = max(i, 1); j < n && j < i + ssq; j++){
            dp[j] = inf;
            if(cht.pt){
                dp[j] = cht.get_max(h[j]) * -1 + w[j - 1] + ll(h[j]) * h[j];
            }
            for(int k = i; 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]);
            av.insert({h[j], j});
            //cout << j << ' ' << dp[j] << endl;
        }
        cht.clear();
        for(auto it = av.begin(); it != av.end(); it++){
            int v = (it -> se);
            //cout << "adding " << v << endl;
            cht.add({w[v] - dp[v] - h[v] * h[v], 2 * h[v]}); // {const, shib}
        }
    }

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1180 ms 11560 KB Output is correct
2 Correct 1164 ms 12248 KB Output is correct
3 Correct 1178 ms 12204 KB Output is correct
4 Correct 1093 ms 12152 KB Output is correct
5 Correct 517 ms 12100 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 1180 ms 11560 KB Output is correct
7 Correct 1164 ms 12248 KB Output is correct
8 Correct 1178 ms 12204 KB Output is correct
9 Correct 1093 ms 12152 KB Output is correct
10 Correct 517 ms 12100 KB Output is correct
11 Correct 1277 ms 12360 KB Output is correct
12 Correct 1301 ms 12260 KB Output is correct
13 Correct 937 ms 12328 KB Output is correct
14 Correct 1234 ms 12440 KB Output is correct
15 Correct 386 ms 12136 KB Output is correct
16 Correct 479 ms 12108 KB Output is correct
17 Correct 227 ms 12268 KB Output is correct
18 Correct 264 ms 12420 KB Output is correct