제출 #964220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964220		pcc	Building Bridges (CEOI17_building)	C++17	100 / 100	56 ms	73348 KiB

building

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const ll inf = 1e18;
const ll mxn = 1e6+10;

struct line{
	ll m,b;
	line(){
		m = 0;
		b = inf;
	}
	line(ll mm,ll bb):m(mm),b(bb){}
	ll operator()(ll x){
		return m*x+b;
	}
};



struct SEG{
	line seg[mxn*4];
	SEG(){}
	void addline(int now,int l,int r,line k){
		if(l == r){
			if(seg[now](l)>k(l))swap(seg[now],k);
			return;
		}
		int mid = (l+r)>>1;
		if(seg[now](mid)>k(mid))swap(seg[now],k);
		if(seg[now].m<k.m)addline(now*2+1,l,mid,k);
		else addline(now*2+2,mid+1,r,k);
		return;
	}
	ll getval(int now,int l,int r,int p){
		if(l == r)return seg[now](p);
		int mid = (l+r)>>1;
		if(mid>=p)return min(seg[now](p),getval(now*2+1,l,mid,p));
		else return min(seg[now](p),getval(now*2+2,mid+1,r,p));
	}
};

SEG seg;
ll H[mxn],pref[mxn];
ll N;
ll dp[mxn];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++)cin>>H[i];
	for(int i = 1;i<=N;i++)cin>>pref[i],pref[i] += pref[i-1];
	seg.addline(0,0,mxn-1,line(-H[1]*2,dp[1]+H[1]*H[1]-pref[1]));
	for(int i = 2;i<=N;i++){
		dp[i] = seg.getval(0,0,mxn-1,H[i])+pref[i-1]+H[i]*H[i];
		seg.addline(0,0,mxn-1,line(-H[i]*2,dp[i]+H[i]*H[i]-pref[i]));
	}
	cout<<dp[N];
}

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