제출 #252056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252056		errorgorn	Building Bridges (CEOI17_building)	C++14	100 / 100	257 ms	128376 KiB

building

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct line{
	ll m,c;
	
	line (ll _m,ll _c){
		m=_m,c=_c;
	}
	
	ll get(ll x){
		return m*x+c;
	}
};

struct node{
	int s,e,m; //[s,e)
	line val=line(0,1e19);
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (e-s>1){
			l=new node(s,m);
			r=new node(m,e);
		}
	}
	
	void update(line i){
		bool left=i.get(s)<val.get(s);
		bool mid=i.get(m)<val.get(m);
		
		if (mid) swap(i,val);
		
		if (e-s>1){
			if (left!=mid) l->update(i);
			else r->update(i);
		}
	}
	
	ll query(ll x){
		if (e-s==1) return val.get(x);
		else if (x<m) return min(l->query(x),val.get(x));
		else return min(r->query(x),val.get(x));
	}
} *root=new node(0,1000005);

ll sq(ll i){
	return i*i;
}

int n;
ll h[100005];
ll w[100005]; //actually pref

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,1,n+1) cin>>h[x];
	rep(x,1,n+1){
		cin>>w[x];
		w[x]+=w[x-1];
	}
	
	root->update(line(-2*h[1],sq(h[1])-w[1]));
	
	ll ans;
	rep(x,2,n+1){
		ans=root->query(h[x])+sq(h[x])+w[x-1];
		//cout<<ans<<endl;
		root->update(line(-2*h[x],sq(h[x])-w[x]+ans));
	}
	
	cout<<ans<<endl;
}

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

building.cpp:48:22: warning: overflow in implicit constant conversion [-Woverflow]
  line val=line(0,1e19);
                      ^
building.cpp: In constructor 'node::node(int, int)':
building.cpp:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

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