oj.uz

답안 #561212

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
561212 2022-05-12T13:16:01 Z fatemetmhr Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 5600 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   = 1;
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 2676 KB Output is correct
4 Correct 24 ms 2776 KB Output is correct
5 Correct 17 ms 2772 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3049 ms 5600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
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 2676 KB Output is correct
4 Correct 24 ms 2776 KB Output is correct
5 Correct 17 ms 2772 KB Output is correct
6 Execution timed out 3049 ms 5600 KB Time limit exceeded
7 Halted 0 ms 0 KB -