oj.uz

Submission #647797

# Submission time Handle Problem Language Result Execution time Memory
647797 2022-10-04T07:06:36 Z ymm Building Bridges (CEOI17_building) C++17
100 / 100
 1539 ms 5472 KB 
#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 ans = 1e100;
	Loop (j,l,r) {
		double tmp = h-::h[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]) - suf_sum[i];
		dsw[i] = dp[i] + suf_sum[i] - w[i];
	}
	cout << (ll)dp[n-1] << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1402 ms 5128 KB Output is correct
2 Correct 1467 ms 5212 KB Output is correct
3 Correct 1489 ms 5128 KB Output is correct
4 Correct 1425 ms 5136 KB Output is correct
5 Correct 1445 ms 5184 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1402 ms 5128 KB Output is correct
7 Correct 1467 ms 5212 KB Output is correct
8 Correct 1489 ms 5128 KB Output is correct
9 Correct 1425 ms 5136 KB Output is correct
10 Correct 1445 ms 5184 KB Output is correct
11 Correct 1406 ms 5408 KB Output is correct
12 Correct 1474 ms 5160 KB Output is correct
13 Correct 1492 ms 5296 KB Output is correct
14 Correct 1539 ms 5388 KB Output is correct
15 Correct 1473 ms 5016 KB Output is correct
16 Correct 1512 ms 5056 KB Output is correct
17 Correct 1520 ms 5232 KB Output is correct
18 Correct 1355 ms 5472 KB Output is correct