Submission #942306

#	Time	Username	Problem	Language	Result	Execution time	Memory
942306		Minbaev	Building Bridges (CEOI17_building)	C++17	100 / 100	53 ms	51024 KiB

building

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define int long long
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int N=1e6 + 5	;
const int inf = 1e18 + 7;
const int mod = 998244353;

pii t[N*4];
vector<int> h(N),w(N);
int sum = 0;

int f(int a, int b, int c){
	return a*b+c;	
}

void build(int tl, int tr, int v){
	t[v] = {1e9,inf};
	
	if(tl == tr)return;
	
	int tm = (tl + tr)/2;
	build(tl,tm,v*2);
	build(tm+1,tr,v*2+1);
}

void add(int tl, int tr, int v, int a, int b){
	
	if(tl == tr){
		if(f(t[v].f,tl,t[v].s) > f(a,tl,b)){
			t[v] = {a,b};
		}
		return;
	}
	
	int tm = (tl + tr)/2;
	
	if(a < t[v].f){
		swap(a,t[v].f);
		swap(b,t[v].s);
	}
	if(f(a,tm,b) >= f(t[v].f,tm,t[v].s))
		add(tl,tm,v*2,a,b);
	else{
		add(tm+1,tr,v*2+1,t[v].f,t[v].s);
		t[v] = {a,b};
	}
}

int get(int tl, int tr, int v, int x){
	if(tl == tr)return f(t[v].f,x,t[v].s);
	
	int tm = (tl + tr)/2;
	if(x <= tm)return min(f(t[v].f,x,t[v].s),get(tl,tm,v*2,x));
	else return min(f(t[v].f,x,t[v].s),get(tm+1,tr,v*2+1,x));

}

void solve(){
	
	int n,m,k;
	
	cin >> n;
	
	for(int i = 1;i<=n;i++){
		cin>>h[i];
	}
	
	for(int i = 1;i<=n;i++){
		cin>>w[i];
		sum += w[i];
	}
	
	build(1,N-1,1);
	
	add(1,N-1,1,-2*h[1],-w[1]+h[1]*h[1]);
	
	vector<int>dp(n+1);
	for(int i = 2;i<=n;i++){
		dp[i] = get(1,N-1 ,1,h[i]) + h[i]*h[i] - w[i];
		add(1,N,1,-2*h[i],dp[i]+h[i]*h[i]);
	}
	
	cout<<dp[n]+sum<<'\n';	
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt>>n;
	while(tt--)solve();

}

Compilation message (stderr)

building.cpp: In function 'void solve()':
building.cpp:74:8: warning: unused variable 'm' [-Wunused-variable]
   74 |  int n,m,k;
      |        ^
building.cpp:74:10: warning: unused variable 'k' [-Wunused-variable]
   74 |  int n,m,k;
      |          ^

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