Submission #652803

#	Time	Username	Problem	Language	Result	Execution time	Memory
652803		ymm	Building Bridges (CEOI17_building)	C++17	100 / 100	1639 ms	4316 KiB

building

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'032;
double h[N], w[N];
double dp[N], suf_sum[N];
double dsw[N];
int n;

__attribute__((optimize("Ofast,unroll-loops"),target("avx2")))
double find_min(int l, int r, double h,
                double inf, double height[], double dsw[])
{
	double ans = inf;
	Loop (j,l,r) {
		double tmp = h-height[j];
		tmp = tmp*tmp;
		tmp += dsw[j];
		ans = ans < tmp? ans: tmp;
	}
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		ll x;
		cin >> x;
		h[i] = x;
	}
	Loop (i,0,n) {
		ll x;
		cin >> x;
		w[i] = x;
	}
	suf_sum[n-1] = w[n-1];
	LoopR (i,0,n-1)
		suf_sum[i] = suf_sum[i+1] + w[i];
	dp[0] = 0;
	dsw[0] = dp[0] + suf_sum[0] - w[0];
	Loop (i,1,n) {
		dp[i] = find_min(0,i,h[i], 1e100,h,dsw) - suf_sum[i];
		dsw[i] = dp[i] + suf_sum[i] - w[i];
	}
	cout << (ll)dp[n-1] << '\n';
}

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