제출 #873507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873507		thienhx	Building Bridges (CEOI17_building)	C++17	100 / 100	35 ms	13400 KiB

building

#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';
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40