oj.uz

Submission #825549

# Submission time Handle Problem Language Result Execution time Memory
825549 2023-08-15T02:37:01 Z Boycl07 Building Bridges (CEOI17_building) C++17
100 / 100
 41 ms 10496 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define int ll
#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pb push_back
#define task "test"
#define endl "\n"
#define sz(a) int(a.size())
#define bit(i, mask) (mask >> i & 1)
#define all(a) (a).begin(), (a).end()

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }


const int N =  1e6 + 2;
const int S = N * 81 + 100;
const int M = 101;
const int K = 1e2 + 1;
const int MOD = 1e9 + 9;
const ll MOD2 = 1e9 + 9;
const int INF = 1e13 + 9999;
const ll LINF = 1e18 + 9999;
const int offset = N;
const int LIM = 1e6 + 2;
const int AL = 26;
const ll P = 1e15;
const int LOG = 16;

int n;

int dp[N], w[N], h[N], sum[N];

bool Q = 0;

struct line
{
    mutable int a, b, p;
    bool operator < (const line &x) const {
        return Q ? p < x.p : a < x.a;
    }
};

struct CHT : multiset<line> {

    int div(int x, int y)
    {
        return x / y - ((x ^ y) < 0 && x % y);
    }

    bool bad(iterator x, iterator y)
    {
        if(y == end()) {x -> p = INF; return 0;}
        if(x -> a == y -> a)
            x -> p = x -> b > y -> b ? INF : -INF;
        else
            x -> p = div(y -> b - x -> b, x -> a - y -> a);
        return x -> p >= y -> p;
    }

    void add(int a, int b)
    {
        auto z = insert({a, b, 0}), y = z++, x = y;
        while(bad(y, z)) z = erase(z);
        if(x != begin() && bad(--x, y)) bad(x, y = erase(y));
        while((y = x) != begin() && (--x) -> p >= y -> p)
            bad(x, erase(y));
    }

    int query(int x)
    {
        Q = 1;
        auto l = *lower_bound({0, 0, x}); Q = 0;
        return l.a * x + l.b;
    }
};

CHT st;

void solve()
{
    cin >> n;
    rep(i, n) cin >> h[i];
    rep(i, n) cin >> w[i], sum[i] = sum[i - 1] + w[i];
    rep(i, n)
    {

        if(i == 1) dp[i] = 0;
        else dp[i] = -st.query(h[i]) + h[i] * h[i] + sum[i - 1];
        st.add(2 * h[i], -(h[i] * h[i] + dp[i] - sum[i]));
    }
    cout << dp[n];
}


signed main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //freopen("building.inp", "r", stdin);
    //freopen("building.out", "w", stdout);

    int TC = 1;
    while(TC--)
    {
        solve();
        cout << endl;
        //reset
        //reset
        //reset
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 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 31 ms 3488 KB Output is correct
2 Correct 33 ms 3504 KB Output is correct
3 Correct 33 ms 4600 KB Output is correct
4 Correct 29 ms 4340 KB Output is correct
5 Correct 27 ms 5568 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 31 ms 3488 KB Output is correct
7 Correct 33 ms 3504 KB Output is correct
8 Correct 33 ms 4600 KB Output is correct
9 Correct 29 ms 4340 KB Output is correct
10 Correct 27 ms 5568 KB Output is correct
11 Correct 30 ms 4632 KB Output is correct
12 Correct 32 ms 4436 KB Output is correct
13 Correct 25 ms 4676 KB Output is correct
14 Correct 38 ms 4616 KB Output is correct
15 Correct 41 ms 10496 KB Output is correct
16 Correct 27 ms 5580 KB Output is correct
17 Correct 22 ms 4568 KB Output is correct
18 Correct 21 ms 4452 KB Output is correct