제출 #477344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477344		2548631	Building Bridges (CEOI17_building)	C++17	100 / 100	54 ms	8860 KiB

building

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;

#define fastIO ios::sync_with_stdio(false), cin.tie(NULL)
#define forw(i, l, r) for( int i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( int i = (r) ; i >= (l) ; i-- )
#define log2i(x) (64 - __builtin_clzll(1ll * (x)) - 1)
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define Pi acos(-1.0l)
#define sz(x) int(x.size())
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';

#pragma once

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

const int N = 1e5 + 7;
int n;
ll h[N], w[N], dp[N];
LineContainer ds;

int main() {
    fastIO;
#ifndef ONLINE_JUDGE
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
#endif

    cin >> n;
    ll sum = 0;
    forw(i, 0, n) cin >> h[i];
    forw(i, 0, n) cin >> w[i], sum += w[i];

    dp[0] = -w[0];
    forw(i, 1, n) {
        ds.add(2 * h[i - 1], - dp[i - 1] - h[i - 1] * h[i - 1]);
        dp[i] = -ds.query(h[i]) + h[i] * h[i] - w[i];
    }
    cout << dp[n - 1] + sum;
    return 0;
}

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

building.cpp:36:9: warning: #pragma once in main file
   36 | #pragma once
      |         ^~~~

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