oj.uz

Submission #159168

# Submission time Handle Problem Language Result Execution time Memory
159168 2019-10-21T11:15:21 Z nvmdava Building Bridges (CEOI17_building) C++17
0 / 100
 27 ms 3704 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 100005

ll h[N], w[N];
ll dp[N];

inline ll sqr(ll a){
	return a * a;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin>>n;

	for(int i = 1; i <= n; i++)
		cin>>h[i];
	for(int i = 1; i <= n; i++){
		cin>>w[i];
		w[i] += w[i - 1];
	}
	memset(dp, 0x3f3f, sizeof dp);
	dp[1] = 0;
	vector<int> d, u;

	for(int i = 1; i <= n; i++){
		while(!d.empty() && h[d.back()] < h[i])
			d.pop_back();
		while(!u.empty() && h[u.back()] > h[i])
			u.pop_back();

		if(!d.empty())
			dp[i] = min(dp[i], dp[d.back()] + sqr(h[i] - h[d.back()]) + w[i - 1] - w[d.back()]);
		if(!u.empty())
			dp[i] = min(dp[i], dp[u.back()] + sqr(h[i] - h[u.back()]) + w[i - 1] - w[u.back()]);

		while(!u.empty() && h[u.back()] == h[i])
			u.pop_back();
		while(!d.empty() && h[d.back()] == h[i])
			d.pop_back();

		u.push_back(i);
		d.push_back(i);
	}

	cout<<dp[n];
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -