oj.uz

Submission #94609

# Submission time Handle Problem Language Result Execution time Memory
94609 2019-01-21T16:07:32 Z jasony123123 Building Bridges (CEOI17_building) C++11
100 / 100
 104 ms 64636 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 data[SZ * 4];

	LiChao() {}

	void init(Line def, int N = SZ) {
		fill(data, data + 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) < data[ind].eval(mid)) swap(nLine, data[ind]);
		if (L == R) return;
		if (nLine.eval(L) < data[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 = data[ind].eval(x);
		if (L < R) {
			if (x <= mid) minn(s, query(x, 2 * ind, L, mid));
			else minn(s, query(x, 2 * ind + 1, mid + 1, R));
		}
		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];
	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 41 ms 63096 KB Output is correct
3 Correct 42 ms 62900 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 82 ms 64504 KB Output is correct
2 Correct 93 ms 64504 KB Output is correct
3 Correct 88 ms 64544 KB Output is correct
4 Correct 83 ms 64636 KB Output is correct
5 Correct 84 ms 64504 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 41 ms 63096 KB Output is correct
3 Correct 42 ms 62900 KB Output is correct
4 Correct 43 ms 62968 KB Output is correct
5 Correct 43 ms 62968 KB Output is correct
6 Correct 82 ms 64504 KB Output is correct
7 Correct 93 ms 64504 KB Output is correct
8 Correct 88 ms 64544 KB Output is correct
9 Correct 83 ms 64636 KB Output is correct
10 Correct 84 ms 64504 KB Output is correct
11 Correct 103 ms 64504 KB Output is correct
12 Correct 102 ms 64572 KB Output is correct
13 Correct 86 ms 64568 KB Output is correct
14 Correct 104 ms 64504 KB Output is correct
15 Correct 86 ms 64508 KB Output is correct
16 Correct 86 ms 64476 KB Output is correct
17 Correct 79 ms 64504 KB Output is correct
18 Correct 79 ms 64504 KB Output is correct