oj.uz

답안 #173140

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
173140 2020-01-03T12:54:09 Z dvdg6566 Building Bridges (CEOI17_building) C++14
30 / 100
 127 ms 3448 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ld> vi;
typedef pair<ld,ld> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define All(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second

typedef ll ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot (point a, point b){
	return (conj(a)*b).x();
}

ftype f(point a, ftype x){
	return dot(a, {x,1});
}

const ll MAXN = 1e6+10;
point line [4*MAXN];
int vis[4*MAXN];

void add_line(point nw, ll v=1, ll l=0, ll r=MAXN){
	ll m=(l+r)/2;
	bool lef = f(nw, l) < f(line[v], l);
	bool mid = f(nw, m) < f(line[v], m);
	if (mid){
		swap(line[v], nw);
	}
	if (r-l == 1)return;
	if (lef != mid)add_line(nw,2*v,l,m);
	else add_line(nw, 2*v+1, m, r);
}

ll get(ll x, ll v=1, ll l=0, ll r=MAXN){
	ll t = f(line[v], x);
	if (line[v].x() == 0 && line[v].y() == 0)t = 1e18;
	// cout<<line[v].x()<<' '<<line[v].y()<<' '<<f(line[v],x)<<'\n';
	ll m=(l+r)/2;
	if (r-l == 1)return t;
	if (x<m)return min(t, get(x, 2*v, l, m));
	else return min(t, get(x,2*v+1,m,r));
}

ll N,H[MAXN], E[MAXN];
ll W;
ll dp[MAXN];
ll d[MAXN];

int main(){
	cin>>N;
	for (ll i=1;i<=N;++i)cin>>H[i];
	for (ll i=1;i<=N;++i)cin>>E[i], W += E[i];
	dp[1] = -E[1];
	add_line({-2*H[1], dp[1] + H[1] * H[1]});
	// cout<<dp[1] + H[1] * H[1]<<' '<<-2*H[1]<<'\n';
	// return 0;
	for (ll i=2;i<=N;++i){
		dp[i] = H[i] * H[i] - E[i] + get(H[i]);
		add_line({-2*H[i], H[i] * H[i] + dp[i]});
		// return 0;
	}
	cout<<dp[N]+W;

}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 4 ms 888 KB Output is correct
5 Correct 4 ms 760 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 3320 KB Output is correct
2 Correct 127 ms 3220 KB Output is correct
3 Correct 127 ms 3320 KB Output is correct
4 Correct 119 ms 3084 KB Output is correct
5 Incorrect 115 ms 3448 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 4 ms 888 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 127 ms 3320 KB Output is correct
7 Correct 127 ms 3220 KB Output is correct
8 Correct 127 ms 3320 KB Output is correct
9 Correct 119 ms 3084 KB Output is correct
10 Incorrect 115 ms 3448 KB Output isn't correct