oj.uz

Submission #45255

# Submission time Handle Problem Language Result Execution time Memory
45255 2018-04-12T08:12:45 Z qoo2p5 Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 7164 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = (int) 1e5 + 123;
const int M = 1 << 20;

int n;
ll h[N], w[N];
ll dp[N], p[N];

struct Line {
	ll k, b;
	
	ll val(ll x) {
		return k * x + b;
	}
};

vector<Line> tmp;

void add(const Line &l) {
	tmp.pb(l);
}

ll get(ll x) {
	ll res = LINF;
	for (auto &it : tmp) {
		mini(res, it.val(x));
	}
	return res;
}

void update(int i) {
	add({-2 * h[i], dp[i] - p[i] + h[i] * h[i]});
}

ll calc(int i) {
	return get(h[i]) + h[i] * h[i] + p[i - 1];
}

void run() {
	cin >> n;
	rep(i, 0, n) {
		cin >> h[i];
	}
	rep(i, 0, n) {
		cin >> w[i];
	}
	
	partial_sum(w, w + n, p);
	rep(i, 0, n) {
		dp[i] = LINF;
	}
	dp[0] = 0;
	update(0);
	rep(i, 1, n) {
		dp[i] = calc(i);
		update(i);
	}
	
	cout << dp[n - 1] << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 532 KB Output is correct
4 Correct 3 ms 532 KB Output is correct
5 Correct 3 ms 652 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 7164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 532 KB Output is correct
4 Correct 3 ms 532 KB Output is correct
5 Correct 3 ms 652 KB Output is correct
6 Execution timed out 3040 ms 7164 KB Time limit exceeded
7 Halted 0 ms 0 KB -