제출 #417525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417525		JerryLiu06	Building Bridges (CEOI17_building)	C++17	100 / 100	84 ms	66504 KiB

building

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define EACH(a,x) for (auto& a: x)
 
const int MOD = 1e9 + 7;
const int MX = 1e6 + 10; 
const ll INF = 1e18; 

// Description: Li Chao Segment Tree. You can add lines of the form kx + m, and query maximum
// values at points x. *Useful for dynamic programming (CHT)* Time: O(lg N)

struct Line {
    ll M, C; Line() { M = 0, C = INF; } Line(ll _M, ll _C) { M = _M; C = _C; }

    ll operator()(ll X) { return M * X + C; }
};

struct LiChaoSegTree {
    Line tree[4 * MX];

    void update(int x, int l, int r, Line line) { int mid = (l + r) / 2;
        bool L = tree[x](l) > line(l); bool M = tree[x](mid) > line(mid); bool R = tree[x](r) > line(r);

        if (L == R) { if (L) swap(line, tree[x]); return ; }

        if (L == M) { if (L) swap(tree[x], line); update(2 * x + 1, mid + 1, r, line); }
        if (M == R) { if (R) swap(tree[x], line); update(2 * x, l, mid, line); }
    }
    ll query(int x, int l, int r, int pos) { int mid = (l + r) / 2;
        if (l == r) return tree[x](pos);
        
        if (pos <= mid) return min(tree[x](pos), query(2 * x, l, mid, pos));
        
        if (pos > mid) return min(tree[x](pos), query(2 * x + 1, mid + 1, r, pos));

        //return min(query(2 * x, l, mid, pos), query(2 * x + 1, mid + 1, r, pos));
    }
};
int N; ll H[MX], W[MX], tot; ll DP[MX]; LiChaoSegTree LC;

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

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

    cin >> N; FOR(i, 1, N + 1) cin >> H[i]; FOR(i, 1, N + 1) cin >> W[i], tot += W[i];

    DP[1] = -W[1]; FOR(i, 2, N + 1) {
        Line cur = Line(-2 * H[i - 1], DP[i - 1] + H[i - 1] * H[i - 1]); LC.update(1, 0, 1e6, cur);

        DP[i] = LC.query(1, 0, 1e6, H[i]) - W[i] + H[i] * H[i];
    }
    cout << tot + DP[N];
}

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

building.cpp: In member function 'll LiChaoSegTree::query(int, int, int, int)':
building.cpp:77:5: warning: control reaches end of non-void function [-Wreturn-type]
   77 |     }
      |     ^

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40