Submission #49309

#	Time	Username	Problem	Language	Result	Execution time	Memory
49309		tmwilliamlin168	Building Bridges (CEOI17_building)	C++14	100 / 100	79 ms	35052 KiB

building

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

#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second

inline int in() {
	bool minus = false;
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch == '-')
			break;
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	if(ch == '-')
		minus = true;
	else
		result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return minus?-result:result;
}
inline void out(ll x) {
	if(x<0) {
		putchar_unlocked('-');
		x=-x;
	}
	ll rev=x;
	int count = 0;
	if(x == 0) {
putchar_unlocked('0');
putchar_unlocked('\n');
return;
}
	while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
	rev = 0;
	while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
	while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
	while(count--)
putchar_unlocked('0');
	putchar_unlocked('\n');
}

const int mxN=1e5, mxH=1e6, sts=1<<21;
int n;
ll h[mxN], pw[mxN+1];
pll st[sts];

void upd(pll nl, int i=1, int l=0, int r=mxH) {
	int m=(l+r)/2;
	if(nl.fi*m+nl.se<st[i].fi*m+st[i].se)
		swap(nl, st[i]);
	if(l==r)
		return;
	if(nl.fi*l+nl.se<st[i].fi*l+st[i].se)
		upd(nl, 2*i, l, m);
	else
		upd(nl, 2*i+1, m+1, r);
}

ll qry(int x, int i=1, int l=0, int r=mxH) {
	int m=(l+r)/2;
	ll s=st[i].fi*x+st[i].se;
	if(l<r) {
		if(x<=m)
			s=min(qry(x, 2*i, l, m), s);
		else
			s=min(qry(x, 2*i+1, m+1, r), s);
	}
	return s;
}

int main() {
	n=in();
	for(int i=0; i<n; ++i)
		h[i]=in();
	for(int i=0; i<n; ++i)
		pw[i+1]=pw[i]+in();
	for(int i=1; i<sts; ++i)
		st[i]={-2*h[0], h[0]*h[0]-pw[1]};
	for(int i=1; i<n; ++i) {
		ll dp=h[i]*h[i]+pw[i]+qry(h[i]);
		upd({-2*h[i], dp-pw[i+1]+h[i]*h[i]});
		if(i==n-1)
			out(dp);
	}
}

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