Submission #1230321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230321		Nika533	Building Bridges (CEOI17_building)	C++20	100 / 100	60 ms	36424 KiB

building

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
const int N=1e5+5,A=1e6+6;
int n,m,T,dp[A],h[A],w[A],pref[A];

struct Line {
	int k,b;
	int operator()(int x) {
		return k*x+b;
	}
} t[A*4];

void build(int v, int tl, int tr) {
	t[v].k=t[v].b=1e12;
	if (tl+1==tr) return;
	int mid=(tl+tr)/2;
	build(v*2,tl,mid); build(v*2+1,mid,tr);
}

void insert(int v, int tl, int tr, Line a) {
	if (tl+1==tr) {
		if (a(tl)<t[v](tl)) t[v]=a;
		return;
	}
	int mid=(tl+tr)/2;
	if (t[v].k>a.k) swap(t[v],a);
	if (t[v](mid)<a(mid)) {
		insert(v*2,tl,mid,a);
	}
	else {
		swap(a,t[v]);
		insert(v*2+1,mid,tr,a);
	}
}
int query(int v, int tl, int tr, int x) {
	if (tl+1==tr) return t[v](x);
	int mid=(tl+tr)/2;
	if (x<mid) return min(t[v](x),query(v*2,tl,mid,x));
	else return min(t[v](x),query(v*2+1,mid,tr,x));
}

void test_case() {
	cin>>n;
	for (int i=1; i<=n; i++) cin>>h[i];
	for (int i=1; i<=n; i++) {
		cin>>w[i];
		pref[i]=pref[i-1]+w[i];
	}
	int mx=1e6+2;
	build(1,1,mx);
	for (int i=1; i<=n; i++) {
		if (i>1) {
			dp[i]=h[i]*h[i]+pref[i-1];
			dp[i]+=query(1,1,mx,h[i]);
		}
		Line a; a.k=-2*h[i]; a.b=-pref[i]+h[i]*h[i]+dp[i];
		insert(1,1,mx,a);
	}
	cout<<dp[n]<<endl;
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1;
	while (T--) test_case();
}

Compilation message (stderr)

building.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
building.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main () {
      | ^~~~

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