oj.uz

Submission #753932

# Submission time Handle Problem Language Result Execution time Memory
753932 2023-06-06T10:47:08 Z Johann Building Bridges (CEOI17_building) C++14
100 / 100
 75 ms 11372 KB 
#include "bits/stdc++.h"
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,tune=native")

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 1LL << 60;

int N;
vi H;
vi W;
ll ans;
vi dp;

struct segment
{
    mutable ll l, r;
    ll m, a;
    int type = 0; // 0 - normal, 1 - compare by l, 2 - compare by m
    bool operator<(const segment &o) const
    {
        if (type == 1 || o.type == 1)
            return l < o.l;
        if (type == 2 || o.type == 2)
            return m > o.m;
        return l < o.l;
    }
};
double intersection(ll m1, ll a1, ll m2, ll a2)
{
    return (a1 - a2) / (double)(m2 - m1);
    // todo parallel???
}
struct convexHull
{
    set<segment> H;
    void insert(ll m, ll a)
    {
        auto it1 = H.lower_bound({0, 0, m, 0, 2});
        if (it1 != H.end() && it1->m == m)
        {
            if (it1->a <= a)
                return;
            it1 = H.erase(it1);
        }
        if (it1 == H.begin())
            it1 = H.end();
        else
        {
            --it1; // the elements with o.m > m
            while (intersection(it1->m, it1->a, m, a) < it1->r)
            {
                double inter = intersection(it1->m, it1->a, m, a);
                if (inter < it1->l)
                    it1 = --H.erase(it1);
                else
                    it1->r = (ll)floor(inter);
            }
        }

        auto it2 = H.upper_bound({0, 0, m, 0, 2});
        while (it2 != H.end() && intersection(it2->m, it2->a, m, a) > it2->l)
        {
            double inter = intersection(it2->m, it2->a, m, a);
            if (inter > it2->r)
                it2 = H.erase(it2);
            else
                it2->l = (ll)ceil(inter);
        }

        if (it1 == H.end() || it2 == H.end() || it1->r + 1 < it2->l)
        {
            H.insert({(it1 == H.end()) ? -INF : it1->r + 1, (it2 == H.end()) ? INF : it2->l - 1, m, a, 0});
        }
    }
    ll query(ll x)
    {
        segment seg = *(--H.upper_bound({x, 0, 0, 0, 1}));
        return seg.m * x + seg.a;
    }
};

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

    cin >> N;
    H.resize(N), W.resize(N), dp.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> H[i];
    for (int i = 0; i < N; ++i)
        cin >> W[i];

    ans = accumulate(all(W), 0LL);

    convexHull hull;
    dp[0] = -W[0];

    hull.insert(-2 * H[0], dp[0] + H[0] * H[0]); // first pillar
    for (int i = 1; i < N; ++i)
    {
        dp[i] = hull.query(H[i]) - W[i] + H[i] * H[i];
        hull.insert(-2 * H[i], dp[i] + H[i] * H[i]);
    }

    cout << dp.back() + ans << endl;

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3680 KB Output is correct
2 Correct 58 ms 3740 KB Output is correct
3 Correct 61 ms 3680 KB Output is correct
4 Correct 55 ms 3624 KB Output is correct
5 Correct 63 ms 5092 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 66 ms 3680 KB Output is correct
7 Correct 58 ms 3740 KB Output is correct
8 Correct 61 ms 3680 KB Output is correct
9 Correct 55 ms 3624 KB Output is correct
10 Correct 63 ms 5092 KB Output is correct
11 Correct 53 ms 3896 KB Output is correct
12 Correct 67 ms 3744 KB Output is correct
13 Correct 34 ms 3796 KB Output is correct
14 Correct 69 ms 3928 KB Output is correct
15 Correct 75 ms 11372 KB Output is correct
16 Correct 68 ms 5084 KB Output is correct
17 Correct 17 ms 3668 KB Output is correct
18 Correct 19 ms 3704 KB Output is correct