Submission #61823

#	Time	Username	Problem	Language	Result	Execution time	Memory
61823		IvanC	Building Bridges (CEOI17_building)	C++17	30 / 100	113 ms	10464 KiB

building

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

typedef long long ll;
typedef long double ld;

const int MAXN = 1e5 + 10;
const int BUCKET = 320;
const ll INF = 1e18;

struct line{
	ll a,b;
	
	line(ll _a = 0,ll _b = 0){
		a = _a;
		b = _b;
	}

	ll get(ll x){return a*x + b;}
	ld get_ld(ld x){return a*x + b;}

	bool operator<(const line& other)const{
		if(a != other.a) return a > other.a;
		return b > other.b;
	}

};

vector<line> hull,light_lines;
ll dp[MAXN],H[MAXN],W[MAXN],pref[MAXN],b[MAXN],a[MAXN];
int N;

ld inter(line l1,line l2){
	return -1.0*ld(l1.b - l2.b)/ld(l1.a - l2.a);
}

bool useless(line l1,line l2,line l3){
	ld x = inter(l1,l3);
	return l2.get_ld(x) >= l3.get_ld(x);
}

void add_line(line l){

	while(!hull.empty() && hull.back().a == l.a){
		hull.pop_back();
	}
	while(!hull.empty() && useless(hull[hull.size()-2],hull.back(),l)){
		hull.pop_back();
	}
	hull.push_back(l);

}

void rebuild(){

	vector<line> temp;
	sort(light_lines.begin(),light_lines.end());
	merge(hull.begin(),hull.end(),light_lines.begin(),light_lines.end(),back_inserter(temp));
	hull.clear();
	light_lines.clear();
	for(line l : temp){
		add_line(l);
	}

}

void add(ll a,ll b){
	line l(a,b);
	light_lines.push_back(l);
	if(light_lines.size() >= BUCKET) rebuild();
}

ll query(ll x){
	ll ans = INF;
	for(line l : light_lines) ans = min(ans, l.get(x) );
	if(hull.empty()) return ans;
	ans = min(ans, hull.back().get(x) );
	int ini = 0,fim = hull.size() - 1,meio;
	while(ini <= fim){
		meio = ini + (fim - ini)/2;
		ll f1 = hull[meio].get(x),f2 = hull[meio+1].get(x);
		ans = min(ans, min(f1,f2) );
		if(f1 < f2){
			fim = meio - 1;
		}
		else{
			ini = meio + 1;
		}
	}
	return ans;
}

int main(){

	scanf("%d",&N);
	for(int i = 1;i<=N;i++){
		scanf("%lld",&H[i]);
	}
	for(int i = 1;i<=N;i++){
		scanf("%lld",&W[i]);
		pref[i] = W[i] + pref[i-1];
	}

	dp[1] = 0;
	a[1] = -2*H[1];
	b[1] = -pref[1] + dp[1] + H[1]*H[1];
	add(a[1],b[1]);

	for(int i = 2;i<=N;i++){
		dp[i] = query(H[i]) + H[i]*H[i] + pref[i-1];
		a[i] = -2*H[i];
		b[i] = -pref[i] + dp[i] + H[i]*H[i];
		add(a[i],b[i]);
	}

	cout << dp[N] << endl;

	return 0;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
building.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&H[i]);
   ~~~~~^~~~~~~~~~~~~~
building.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&W[i]);
   ~~~~~^~~~~~~~~~~~~~

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