Submission #252008

#	Time	Username	Problem	Language	Result	Execution time	Memory
252008		lyc	Building Bridges (CEOI17_building)	C++14	30 / 100	143 ms	5248 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;
using ii=pair<int,int>;

const int mxN = 1e5+5;

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

struct Line {
	ll m, c;
	ll eval(ll x) { return m*x + c; }
};

struct Hull {
	Line dq[mxN];
	int s, e;
	
	inline void reset() { s = e = 0; }
	
	Hull() { reset(); }
	
	inline ld intersect(Line a, Line b) {
		return (ld)(a.c - b.c) / (b.m - a.m);
	}
	
	void add(ll m, ll b) {
		Line l = {m,b};
		while (e-s > 1 && intersect(l,dq[e-1]) <= intersect(dq[e-1],dq[e-2])) --e;
		dq[e++] = l;
	}
	
	ll query(ll x) {
		while (e-s > 1 && dq[s].eval(x) >= dq[s+1].eval(x)) ++s;
		return dq[s].eval(x);
	}
} ch;

void cdq(int l, int r) {
	if (l == r) return;
	int m = (l+r)/2;
	cdq(l,m);
	
	ch.reset();
	vector<ii> slopes, queries;
	FOR(i,l,m){
		slopes.emplace_back(-2*H[i],i);
	}
	FOR(i,m+1,r){
		queries.emplace_back(H[i],i);
	}
	sort(ALL(slopes),greater<ii>());
	sort(ALL(queries));
	
	// (H[i]-H[j])^2 + pW[i-1]-pW[j] + dp[j];
	for (auto& s : slopes) {
		int i = s.second;
		ch.add(-2*H[i], SQ(H[i]) - pW[i] + dp[i]);
	}
	for (auto& q : queries) {
		int i = q.second;
		dp[i] = min(dp[i], ch.query(H[i]) + SQ(H[i]) + pW[i-1]);
	}
	
	cdq(m+1,r);
}

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;
    FOR(i,2,N) dp[i] = 1e18;
    cdq(1,N);
	cout << dp[N] << '\n';
}

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