oj.uz

Submission #94602

# Submission time Handle Problem Language Result Execution time Memory
94602 2019-01-21T15:47:15 Z jasony123123 Building Bridges (CEOI17_building) C++11
100 / 100
 159 ms 65804 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/********************CEOI 2017 Day 2 Problem 1******************************/

struct Line {
	ll m, b;
	Line() {}
	Line(ll _m, ll _b) : m(_m), b(_b) {}
	ll eval(int x) {
		return m*x + b;
	}
};

template <int SZ> struct LiChao {
	int n;
	Line st[SZ * 4];

	LiChao() {}

	void init(Line def, int N = SZ*4) {
		fill(st, st + N, def);
	}

	void upd(Line nLine, int ind = 1, int L = 0, int R = SZ - 1) {
		int mid = (L + R) / 2;
		if (nLine.eval(mid) < st[ind].eval(mid)) swap(nLine, st[ind]);
		if (L == R) return;
		if (nLine.eval(L) < st[ind].eval(L)) upd(nLine, 2 * ind, L, mid);
		else upd(nLine, 2 * ind + 1, mid + 1, R);
	}

	ll query(int x, int ind = 1, int L = 0, int R = SZ - 1) {
		int mid = (L + R) / 2;
		ll s = st[ind].eval(x);
		if (L < R) {
			if (x <= mid) s = min(query(x, 2 * ind, L, mid), s);
			else s = min(query(x, 2 * ind + 1, mid + 1, R), s);
		}
		return s;
	}
};

const int MAXN = 100000;
int N;
ll H[MAXN], W[MAXN];
LiChao<1000099> tree;

int main() {
	io();
	cin >> N;
	FOR(i, 0, N) cin >> H[i];
	FOR(i, 0, N) cin >> W[i];
	FOR(i, 1, N) W[i] += W[i - 1];
//	darr(W, N);
//	darr(H, N);
	tree.init(Line(-2 * H[0], H[0] * H[0] + 0 - W[0]));
	FOR(i, 1, N) {
		ll dp = tree.query(H[i]) + W[i - 1] + H[i] * H[i];
		if (i == N - 1) {
			cout << dp << "\n";
		}
		tree.upd(Line(-2 * H[i], H[i] * H[i] + dp - W[i]));
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62968 KB Output is correct
2 Correct 43 ms 62968 KB Output is correct
3 Correct 44 ms 62968 KB Output is correct
4 Correct 43 ms 62968 KB Output is correct
5 Correct 43 ms 62968 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 65528 KB Output is correct
2 Correct 85 ms 65680 KB Output is correct
3 Correct 159 ms 65528 KB Output is correct
4 Correct 81 ms 65528 KB Output is correct
5 Correct 85 ms 65528 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62968 KB Output is correct
2 Correct 43 ms 62968 KB Output is correct
3 Correct 44 ms 62968 KB Output is correct
4 Correct 43 ms 62968 KB Output is correct
5 Correct 43 ms 62968 KB Output is correct
6 Correct 85 ms 65528 KB Output is correct
7 Correct 85 ms 65680 KB Output is correct
8 Correct 159 ms 65528 KB Output is correct
9 Correct 81 ms 65528 KB Output is correct
10 Correct 85 ms 65528 KB Output is correct
11 Correct 106 ms 65804 KB Output is correct
12 Correct 106 ms 65500 KB Output is correct
13 Correct 88 ms 65744 KB Output is correct
14 Correct 106 ms 65756 KB Output is correct
15 Correct 86 ms 65444 KB Output is correct
16 Correct 87 ms 65460 KB Output is correct
17 Correct 79 ms 65668 KB Output is correct
18 Correct 80 ms 65656 KB Output is correct