oj.uz

Submission #94603

# Submission time Handle Problem Language Result Execution time Memory
94603 2019-01-21T15:49:13 Z jasony123123 Building Bridges (CEOI17_building) C++11
100 / 100
 107 ms 64604 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) {}
	inline 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) {
		fill(st, st + N*4, 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<1000001> 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 43 ms 62968 KB Output is correct
2 Correct 51 ms 62968 KB Output is correct
3 Correct 42 ms 62940 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 84 ms 64508 KB Output is correct
2 Correct 94 ms 64504 KB Output is correct
3 Correct 84 ms 64504 KB Output is correct
4 Correct 81 ms 64504 KB Output is correct
5 Correct 86 ms 64504 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 62968 KB Output is correct
2 Correct 51 ms 62968 KB Output is correct
3 Correct 42 ms 62940 KB Output is correct
4 Correct 43 ms 62968 KB Output is correct
5 Correct 43 ms 62968 KB Output is correct
6 Correct 84 ms 64508 KB Output is correct
7 Correct 94 ms 64504 KB Output is correct
8 Correct 84 ms 64504 KB Output is correct
9 Correct 81 ms 64504 KB Output is correct
10 Correct 86 ms 64504 KB Output is correct
11 Correct 107 ms 64564 KB Output is correct
12 Correct 104 ms 64576 KB Output is correct
13 Correct 90 ms 64604 KB Output is correct
14 Correct 101 ms 64476 KB Output is correct
15 Correct 85 ms 64504 KB Output is correct
16 Correct 84 ms 64504 KB Output is correct
17 Correct 80 ms 64504 KB Output is correct
18 Correct 78 ms 64504 KB Output is correct