oj.uz

Submission #873507

# Submission time Handle Problem Language Result Execution time Memory
873507 2023-11-15T08:14:09 Z thienhx Building Bridges (CEOI17_building) C++17
100 / 100
 35 ms 13400 KB 
#include <bits/stdc++.h>
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using db = double;

///--------------------------------

#define           F   first
#define           S   second
#define          pb   push_back
#define          lb   lower_bound
#define          ub   upper_bound
#define       sz(x)   (int)((x).size())
#define      all(x)   (x).begin(), (x).end()
#define     rall(x)   (x).rbegin(), (x).rend()
#define   mem(f, x)   memset(f, x, sizeof(f))
#define  uniqueV(x)   sort(all(x)), (x).resize(unique(all(x)) - x.begin())

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

///--------------------------------

#define PROBLEM "test"

const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const ld eps = 1e-9;
const ld PI = acos(-1);
const int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0}; // R D L U
const int ddx[4]{-1, 1, 1, -1}, ddy[4]{1, 1, -1, -1}; // UR DR DL UL

///--------------------------------

void precalc();
void solve();

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    if (fopen(PROBLEM".inp", "r")) {
        freopen(PROBLEM".inp", "r", stdin);
        freopen(PROBLEM".out", "w", stdout);
    }

    constexpr bool MULTI_TEST = 0;

    int t = 1;
    if (MULTI_TEST) cin >> t;

    while (t--)
        solve();
    
    // cerr << setprecision(3) << fixed;
    // cerr << "[" << 1.0 * clock() / CLOCKS_PER_SEC << "s]  ";
}

///--------------------[PROBLEM SOLUTION]--------------------///

struct Line {
    ll m, b;

    Line(ll _m = 0, ll _b = INF * 8) : m(_m), b(_b) { }
};

ll F(Line l, ll x) {
    return l.m * x + l.b;
}

struct lichao_t {
    lichao_t *left = nullptr, *right = nullptr;
    Line mn;

    lichao_t(ll tl = 0, ll tr = 0) { }

    void Update(ll tl, ll tr, Line nLine) {
        ll mid = (tl + tr) >> 1;

        bool pLeft = (F(nLine, tl) < F(mn, tl));
        bool pMid = (F(nLine, mid) < F(mn, mid));

        if (pMid) swap(mn, nLine);

        if (tl == tr) return;

        if (pLeft != pMid) {
            if (left == nullptr) left = new lichao_t();

            left->Update(tl, mid, nLine);
        }
        else {
            if (right == nullptr) right = new lichao_t();

            right->Update(mid + 1, tr, nLine);
        }
    }

    ll Query(ll tl, ll tr, ll x) {
        if (tl == tr) return F(mn, x);

        ll mid = (tl + tr) >> 1;

        ll res = F(mn, x);

        if (x <= mid) {
            if (left != nullptr)
                minimize(res, left->Query(tl, mid, x));
        }
        else {
            if (right != nullptr)
                minimize(res, right->Query(mid + 1, tr, x));
        }

        return res;
    }
};

//dp[i] = min_j(dp[j] + prefW[i - 1] - prefeW[j] + h[i]^2 - 2 * h[i] * h[j] + h[j]^2);

void solve() {
    ll n;
    cin >> n;

    ll h[n + 1], w[n + 1], pref[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> h[i];

    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        pref[i] = pref[i - 1] + w[i];
    }

    ll dp[n + 1];
    dp[1] = 0;

    lichao_t lc(0, 1e6);
    lc.Update(0, 1e6, Line(-2 * h[1], dp[1] + h[1] * h[1] - pref[1]));

    for (int i = 2; i <= n; i++) {
        dp[i] = h[i] * h[i] + pref[i - 1] + lc.Query(0, 1e6, h[i]);

        lc.Update(0, 1e6, Line(-2 * h[i], dp[i] + h[i] * h[i] - pref[i]));
    }

    cout << dp[n] << '\n';
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(PROBLEM".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(PROBLEM".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5040 KB Output is correct
2 Correct 32 ms 4960 KB Output is correct
3 Correct 32 ms 4952 KB Output is correct
4 Correct 30 ms 4440 KB Output is correct
5 Correct 32 ms 8528 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 34 ms 5040 KB Output is correct
7 Correct 32 ms 4960 KB Output is correct
8 Correct 32 ms 4952 KB Output is correct
9 Correct 30 ms 4440 KB Output is correct
10 Correct 32 ms 8528 KB Output is correct
11 Correct 34 ms 5716 KB Output is correct
12 Correct 35 ms 6276 KB Output is correct
13 Correct 32 ms 4700 KB Output is correct
14 Correct 35 ms 6228 KB Output is correct
15 Correct 29 ms 13400 KB Output is correct
16 Correct 29 ms 8700 KB Output is correct
17 Correct 16 ms 4440 KB Output is correct
18 Correct 16 ms 4448 KB Output is correct