oj.uz

Submission #543238

# Submission time Handle Problem Language Result Execution time Memory
543238 2022-03-29T23:27:20 Z fcw Building Bridges (CEOI17_building) C++17
100 / 100
 51 ms 10588 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

struct Line {
	mutable lint k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(lint x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const lint inf = LLONG_MAX;
	lint div(lint a, lint b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) { x->p = inf; return false; }
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(lint k, lint m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	lint query(lint x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin>>n;
	vector<lint>h(n), w(n);
	for(int i=0;i<n;i++) cin>>h[i];
	for(int i=0;i<n;i++) cin>>w[i];
	vector<lint>pref(n+1);
	for(int i=0;i<n;i++) pref[i+1] = pref[i] + w[i];
	LineContainer g;
	g.add(2 * h[0], -h[0] * h[0] + pref[1]);
	vector<lint>dp(n);
	for(int i=1;i<n;i++){
		dp[i] = h[i] * h[i] + pref[i] - g.query(h[i]);
		g.add(2 * h[i], -h[i] * h[i] + pref[i+1] - dp[i]);
	}
	cout<<dp[n-1]<<"\n";
	
	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 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 38 ms 3432 KB Output is correct
2 Correct 45 ms 4440 KB Output is correct
3 Correct 41 ms 4452 KB Output is correct
4 Correct 35 ms 4404 KB Output is correct
5 Correct 35 ms 5520 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 38 ms 3432 KB Output is correct
7 Correct 45 ms 4440 KB Output is correct
8 Correct 41 ms 4452 KB Output is correct
9 Correct 35 ms 4404 KB Output is correct
10 Correct 35 ms 5520 KB Output is correct
11 Correct 36 ms 4564 KB Output is correct
12 Correct 38 ms 4592 KB Output is correct
13 Correct 31 ms 4576 KB Output is correct
14 Correct 37 ms 4692 KB Output is correct
15 Correct 51 ms 10588 KB Output is correct
16 Correct 36 ms 5604 KB Output is correct
17 Correct 22 ms 4436 KB Output is correct
18 Correct 21 ms 4460 KB Output is correct