oj.uz

Submission #49308

# Submission time Handle Problem Language Result Execution time Memory
49308 2018-05-25T12:04:03 Z tmwilliamlin168 Building Bridges (CEOI17_building) C++14
100 / 100
 133 ms 35044 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() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	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 29 ms 33144 KB Output is correct
2 Correct 26 ms 33144 KB Output is correct
3 Correct 24 ms 33160 KB Output is correct
4 Correct 28 ms 33416 KB Output is correct
5 Correct 26 ms 33416 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 34936 KB Output is correct
2 Correct 133 ms 34936 KB Output is correct
3 Correct 64 ms 34936 KB Output is correct
4 Correct 64 ms 34976 KB Output is correct
5 Correct 60 ms 34976 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 33144 KB Output is correct
2 Correct 26 ms 33144 KB Output is correct
3 Correct 24 ms 33160 KB Output is correct
4 Correct 28 ms 33416 KB Output is correct
5 Correct 26 ms 33416 KB Output is correct
6 Correct 64 ms 34936 KB Output is correct
7 Correct 133 ms 34936 KB Output is correct
8 Correct 64 ms 34936 KB Output is correct
9 Correct 64 ms 34976 KB Output is correct
10 Correct 60 ms 34976 KB Output is correct
11 Correct 75 ms 34976 KB Output is correct
12 Correct 78 ms 35012 KB Output is correct
13 Correct 59 ms 35044 KB Output is correct
14 Correct 77 ms 35044 KB Output is correct
15 Correct 58 ms 35044 KB Output is correct
16 Correct 63 ms 35044 KB Output is correct
17 Correct 47 ms 35044 KB Output is correct
18 Correct 47 ms 35044 KB Output is correct