제출 #251994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251994		lyc	Building Bridges (CEOI17_building)	C++14	100 / 100	160 ms	12920 KiB

building

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SQ(x) ((ll)(x)*(x))
using ll=long long;
using ld=long double;

const int mxN = 1e5+5;

int N, H[mxN], W[mxN];
ll pW[mxN], dp[mxN];

const ll is_query = -(1LL<<62);

struct Line {
	ll m, c;
	mutable function<const Line*()> succ;
	bool operator < (const Line& rhs) const {
		if (rhs.c != is_query) return m > rhs.m;
		auto s = succ();
		if (!s) return 0;
		ll x = rhs.m;
		return (m - s->m)*x > (s->c - c);
	}
};

struct HullDynamic : multiset<Line> {
	bool bad(iterator y) {
		auto z = next(y);
		if (y == begin()) {
			if (z == end()) return 0;
			return y->m == z->m && y->c >= z->c;
		}
		auto x = prev(y);
		if (z == end()) return y->m == x->m && y->c >= x->c;
		if (y->m == x->m) return y->c >= x->c;
		if (y->m == z->m) return y->c >= z->c;
		return (ld)(y->c - z->c)/(z->m - y->m) <= (y->c - x->c)/(x->m - y->m);
	}
	
	void add(ll m, ll c) {
		auto y = insert({ m,c });
		y->succ = [=]{ return next(y) == end() ? 0 : &*next(y); };
		if (bad(y)) { erase(y); return; }
		while (y != begin() && bad(prev(y))) erase(prev(y));
		while (next(y) != end() && bad(next(y))) erase(next(y));
	}
	
	ll query(int x) {
		auto l = *lower_bound({ x,is_query });
		return l.m*x + l.c;
	}
} ch;

int main() {
	//freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    FOR(i,1,N){ cin >> H[i]; }
    FOR(i,1,N){ cin >> W[i]; pW[i] = pW[i-1] + W[i]; }
    
    dp[1] = 0;
    ch.add(-2*H[1], SQ(H[1]) - pW[1] + dp[1]);
    FOR(i,2,N){
		// (H[i]-H[j])^2 + pW[i-1]-pW[j] + dp[j];
		dp[i] = ch.query(H[i]) + SQ(H[i]) + pW[i-1];
		ch.add(-2*H[i], SQ(H[i]) - pW[i] + dp[i]);
		//~ TRACE(i);
		//~ for (auto x : ch) cout << x.m << ' ' << x.c << " | ";
		//~ cout << endl;
	}
	cout << dp[N] << '\n';
}

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