oj.uz

Submission #49307

# Submission time Handle Problem Language Result Execution time Memory
49307 2018-05-25T12:03:27 Z tmwilliamlin168 Building Bridges (CEOI17_building) C++14
100 / 100
 122 ms 35084 KB 
#include <bits/stdc++.h>
using namespace std;

#define getchar_unlocked getchar
#define putchar_unlocked putchar
#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 27 ms 33144 KB Output is correct
2 Correct 26 ms 33256 KB Output is correct
3 Correct 27 ms 33308 KB Output is correct
4 Correct 122 ms 33356 KB Output is correct
5 Correct 31 ms 33356 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 34840 KB Output is correct
2 Correct 81 ms 34972 KB Output is correct
3 Correct 69 ms 35000 KB Output is correct
4 Correct 75 ms 35000 KB Output is correct
5 Correct 64 ms 35084 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33144 KB Output is correct
2 Correct 26 ms 33256 KB Output is correct
3 Correct 27 ms 33308 KB Output is correct
4 Correct 122 ms 33356 KB Output is correct
5 Correct 31 ms 33356 KB Output is correct
6 Correct 71 ms 34840 KB Output is correct
7 Correct 81 ms 34972 KB Output is correct
8 Correct 69 ms 35000 KB Output is correct
9 Correct 75 ms 35000 KB Output is correct
10 Correct 64 ms 35084 KB Output is correct
11 Correct 82 ms 35084 KB Output is correct
12 Correct 83 ms 35084 KB Output is correct
13 Correct 86 ms 35084 KB Output is correct
14 Correct 76 ms 35084 KB Output is correct
15 Correct 59 ms 35084 KB Output is correct
16 Correct 63 ms 35084 KB Output is correct
17 Correct 52 ms 35084 KB Output is correct
18 Correct 77 ms 35084 KB Output is correct