제출 #380545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380545		mariowong	Building Bridges (CEOI17_building)	C++14	0 / 100	200 ms	6880 KiB

building

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


struct cht{
	long long dpval,hgt,psum,indx;
}b;
vector <cht> v;
vector <pair<long long,long long>  > now;
long long n,dp[100005],h[100005],w[100005],ps[100005],a[100005],l,r;
long long lft,rht,midd,indx;
bool cmp(cht a1,cht a2){
	return ((a1.hgt < a2.hgt) || (a1.hgt == a2.hgt) && a1.psum < a2.psum);
}
long double m(int j,int k){
	if (h[j] == h[k])
	return 1e18;
	return (long double)((dp[j]-ps[j]+h[j]*h[j])-(dp[k]-ps[k]+h[k]*h[k]))/(long double)(2*(h[j]-h[k]));
}
void solve(int x,int y){
	if (x == y);
	else
	{
		int mid=(x+y)/2;
		solve(x,mid);
		l=1; r=1; v.clear(); now.clear();
		for (int i=x;i<=mid;i++){
			b.dpval=dp[i]; b.hgt=h[i]; b.psum=ps[i]; b.indx=i;
			v.push_back(b);
		}
		sort(v.begin(),v.end(),cmp);
		for (int i=0;i<v.size();i++){
			while (r-l >= 2 && m(a[r-2],a[r-1]) > m(a[r-1],v[i].indx)) r--;
			a[r]=v[i].indx; r++; 
		}
		for (int i=mid+1;i<=y;i++){
			now.push_back(make_pair(h[i],i));
		}
		sort(now.begin(),now.end()); reverse(now.begin(),now.end());
		for (int i=0;i<now.size();i++){
			while (r-l >= 2 && m(a[l],a[l+1]) <= now[i].first) l++;
			indx=now[i].second;
			dp[indx]=min(dp[indx],dp[a[l]]+ps[indx-1]-ps[a[l]]+(h[indx]-h[a[l]])*(h[indx]-h[a[l]]));
		}
		solve(mid+1,y);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> h[i];
		if (i != 1)
		dp[i]=1e18;
	}
	for (int i=1;i<=n;i++){
		cin >> w[i];
		ps[i]=ps[i-1]+w[i]; 
	}
	solve(1,n);
	cout << dp[n] << "\n";
	return 0;
}	

컴파일 시 표준 에러 (stderr) 메시지

building.cpp: In function 'bool cmp(cht, cht)':
building.cpp:13:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   13 |  return ((a1.hgt < a2.hgt) || (a1.hgt == a2.hgt) && a1.psum < a2.psum);
      |                               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
building.cpp: In function 'void solve(int, int)':
building.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cht>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int i=0;i<v.size();i++){
      |                ~^~~~~~~~~
building.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int i=0;i<now.size();i++){
      |                ~^~~~~~~~~~~

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