oj.uz

Submission #49309

# Submission time Handle Problem Language Result Execution time Memory
49309 2018-05-25T12:05:29 Z tmwilliamlin168 Building Bridges (CEOI17_building) C++14
100 / 100
 79 ms 35052 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33144 KB Output is correct
2 Correct 26 ms 33252 KB Output is correct
3 Correct 26 ms 33252 KB Output is correct
4 Correct 26 ms 33328 KB Output is correct
5 Correct 28 ms 33380 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 34840 KB Output is correct
2 Correct 65 ms 34872 KB Output is correct
3 Correct 65 ms 34896 KB Output is correct
4 Correct 57 ms 34900 KB Output is correct
5 Correct 54 ms 34976 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33144 KB Output is correct
2 Correct 26 ms 33252 KB Output is correct
3 Correct 26 ms 33252 KB Output is correct
4 Correct 26 ms 33328 KB Output is correct
5 Correct 28 ms 33380 KB Output is correct
6 Correct 61 ms 34840 KB Output is correct
7 Correct 65 ms 34872 KB Output is correct
8 Correct 65 ms 34896 KB Output is correct
9 Correct 57 ms 34900 KB Output is correct
10 Correct 54 ms 34976 KB Output is correct
11 Correct 67 ms 34976 KB Output is correct
12 Correct 65 ms 34976 KB Output is correct
13 Correct 53 ms 34976 KB Output is correct
14 Correct 79 ms 34976 KB Output is correct
15 Correct 60 ms 35052 KB Output is correct
16 Correct 58 ms 35052 KB Output is correct
17 Correct 49 ms 35052 KB Output is correct
18 Correct 58 ms 35052 KB Output is correct