Submission #1131722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131722		Champ_Naman	Building Bridges (CEOI17_building)	C++20	100 / 100	83 ms	10568 KiB

building

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'

const int N = 1e5+1;
int dp[N];

struct Line {
	bool type;
	double x;
	int m, c;
};

bool operator<(Line l1, Line l2) {
	if (l1.type || l2.type) return l1.x < l2.x;
	return l1.m > l2.m;
}

set<Line> cht;

bool has_prev(set<Line>::iterator it) { return it != cht.begin(); }
bool has_next(set<Line>::iterator it) {
	return it != cht.end() && next(it) != cht.end();
}

double intersect(set<Line>::iterator l1, set<Line>::iterator l2) {
	return (double)(l1->c - l2->c) / (l2->m - l1->m);
}

void calc_x(set<Line>::iterator it) {
	if (has_prev(it)) {
		Line l = *it;
		l.x = intersect(prev(it), it);
		cht.insert(cht.erase(it), l);
	}
}

bool bad(set<Line>::iterator it) {
	if (has_next(it) && next(it)->c <= it->c) return true;
	return (has_prev(it) && has_next(it) &&
	        intersect(prev(it), next(it)) <= intersect(prev(it), it));
}

void add_line(int m, int c) {
	set<Line>::iterator it;

	it = cht.lower_bound({0, 0, m, c});
	if (it != cht.end() && it->m == m) {
		if (it->c <= c) return;
		cht.erase(it);
	}

	it = cht.insert({0, 0, m, c}).first;
	if (bad(it)) cht.erase(it);
	else {
		while (has_prev(it) && bad(prev(it))) cht.erase(prev(it));
		while (has_next(it) && bad(next(it))) cht.erase(next(it));

		if (has_next(it)) calc_x(next(it));
		calc_x(it);
	}
}

int query(int h){
	Line l = *prev(cht.upper_bound({1, (double)h, 0, 0}));
	return l.m * h + l.c;
}

inline void solve(){
   int n;
   cin>>n;
   int h[n+1], w[n+1], pre[n+1];
   pre[0] = 0;
   for(int i=1; i<=n; i++) cin>>h[i];
   for(int i=1; i<=n; i++) cin>>pre[i], pre[i] += pre[i-1];

   add_line(-h[1], h[1]*h[1] - pre[1]);
   for(int i=2; i<=n; i++){
      dp[i] = query(2*h[i]) + h[i]*h[i] + pre[i-1];
      add_line(-h[i], dp[i] + h[i]*h[i] - pre[i]);
   }

   cout<<dp[n];
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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