제출 #1313023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313023		boclobanchat	Building Bridges (CEOI17_building)	C++20	30 / 100	629 ms	5872 KiB

building

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int sqr=320;
const long long INF=1e18;
double intersect(pair<long long,long long> a,pair<long long,long long> b)
{
	if(a.first==b.first) return INF;
	return (double)(b.second-a.second)/(a.first-b.first);
}
long long dp[MAXN],pref[MAXN],H[MAXN],cnt[MAXN];
double range[MAXN/sqr+5][sqr+5];
vector< pair<long long,long long> > vi[MAXN/sqr+5];
void build(int l,int r,int idx)
{
	vector< pair<long long,long long> > vv;
	for(int i=l;i<=r;i++) vv.push_back({-H[i]*2,dp[i]+H[i]*H[i]-pref[i]});
	sort(vv.begin(),vv.end(),greater< pair<long long,long long> >());
	range[idx][0]=-INF,range[idx][1]=INF;
	for(auto v:vv)
	{
		while(!vi[idx].empty()&&range[idx][cnt[idx]]>intersect(v,vi[idx].back())) cnt[idx]--,vi[idx].pop_back();
		if(!vi[idx].empty()) range[idx][++cnt[idx]]=intersect(v,vi[idx].back()),range[idx][cnt[idx]+1]=INF;
		vi[idx].push_back(v);
	}
}
long long get(int idx,long long val)
{
	int pos=upper_bound(range[idx],range[idx]+cnt[idx]+2,val)-range[idx]-1;
	return vi[idx][pos].first*val+vi[idx][pos].second;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int pre=1,cnt=0;
	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];
		if(i==1) dp[i]=0;
		else
		{
			dp[i]=INF;
			for(int j=pre;j<i;j++) dp[i]=min(dp[i],dp[j]+pref[i-1]-pref[j]+(H[i]-H[j])*(H[i]-H[j]));
			for(int j=1;j<=cnt;j++) dp[i]=min(dp[i],get(j,H[i])+H[i]*H[i]+pref[i-1]);
			if(i%sqr==0)
			{
				pre=i+1;
				build(pre-sqr,i,++cnt);
			}
		}
	}
	cout<<dp[n];
}

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