Submission #1285704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285704		WH8	Building Bridges (CEOI17_building)	C++20	100 / 100	160 ms	128792 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())

struct line{
	int m, c;
	line(){m=0, c=1e12;}
	line (int M, int C){m=M,c=C;}
	int operator () (int x){
		return m*x+c;
	}
};
struct node {
	int s, e, m;
	line v;
	node *l, *r;
	node (int S, int E){
		s=S,e=E,m=(s+e)/2;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1, e);
		}
	}
	void upd(line nw){
		if(nw(s) < v(s))swap(nw, v);
		if(v(e)<nw(e)) return;
		if(s==e)return;
		if(v(m)<nw(m)) r->upd(nw);
		else {
			swap(v, nw);
			l->upd(nw);
		}
		//~ printf("the line at segment %lld %lld is m %lld, c %lld\n", s,e,v.m,v.c);
		//~ cout<<endl;
	}
	int qry(int x){
		if(s==e)return v(x);
		if(x <= m)return min(v(x),l->qry(x));
		return min(v(x), r->qry(x));
	}
}*root;

signed main(){
	int n;cin>>n;
	vector<int> h(n), w(n);
	for(int i=0;i<n;i++)cin>>h[i];
	for(int i=0;i<n;i++)cin>>w[i];
	vector<int> p(n); p[0]=w[0];
	for(int i=1;i<n;i++) p[i]=p[i-1]+w[i];
	root=new node(0, 1e6);
	vector<int> dp(n, 1e15); dp[0]=0;
	root->upd(line(-2*h[0],h[0]*h[0]-p[0]+dp[0]));

	for(int i=1;i<n;i++){
		int mn=root->qry(h[i]);
		dp[i]=mn+h[i]*h[i]+p[i-1];
		root->upd(line(-2*h[i],h[i]*h[i]-p[i]+dp[i]));
		//~ printf("i %lld, mn %lld, dp val %lld\n", i, mn, dp[i]);
	}
	cout<<dp[n-1];
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0

5 
1 2 3 4 5 
1 -100 -100 -100 5
*/

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