Submission #1250059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250059		PlayVoltz	Building Bridges (CEOI17_building)	C++20	100 / 100	41 ms	9796 KiB

building

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

struct line{
	int m, c;
	line (): m(0), c(LLONG_MAX){}//for min change LLONG_MIN to LLONG_MAX
	line (int m, int c): m(m), c(c){}
	int operator()(int x){return m*x+c;}
	bool operator==(line y){return m==y.m&&c==y.c;}
};

struct node{
	int s, e, m;
	line sth;
	node *l, *r;
	node(int s, int e): s(s), e(e), m((s+e)/2), l(nullptr), r(nullptr){}
	void create(){
		if (l!=nullptr)return;
		l = new node(s, m);
		r = new node(m, e);
	}
	void up(line nl){
		bool left = nl(s)<sth(s), mid = nl(m)<sth(m), right = nl(e)<sth(e);//for min change all > to <
		if (mid)swap(sth, nl);
		if (e-s==1 || nl==line() || left==right)return;
		create();
		if (left!=mid)l->up(nl);
		else r->up(nl);
	}
	int query(int x){
		if (e-s==1)return sth(x);
		if (l==nullptr)return sth(x);
		if (x<m)return min(sth(x), l->query(x));//for min change max to min
		else return min(sth(x), r->query(x));//for min change max to min
	}
}*lct;

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<int> dp(n);
	vector<pii> vect(n);
	for (int i=0; i<n; ++i)cin>>vect[i].fi;
	for (int i=0; i<n; ++i)cin>>vect[i].se;
	lct = new node(0, 1000005);
	lct->up(line(-2*vect[0].fi, vect[0].fi*vect[0].fi-vect[0].se));
	for (int i=1, sum=0; i<n; ++i){
		sum+=vect[i-1].se;
		dp[i]=lct->query(vect[i].fi)+vect[i].fi*vect[i].fi+sum;
		lct->up(line(-2*vect[i].fi, vect[i].fi*vect[i].fi+dp[i]-sum-vect[i].se));
	}
	cout<<dp[n-1];
}

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