oj.uz

Submission #94575

# Submission time Handle Problem Language Result Execution time Memory
94575 2019-01-21T04:54:40 Z jasony123123 Building Bridges (CEOI17_building) C++11
30 / 100
 85 ms 64508 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(int _m, int _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) {
		fill(st, st + SZ * 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<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];
	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 48 ms 62968 KB Output is correct
2 Correct 49 ms 62968 KB Output is correct
3 Correct 49 ms 63096 KB Output is correct
4 Correct 50 ms 62968 KB Output is correct
5 Correct 49 ms 62968 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 64508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 62968 KB Output is correct
2 Correct 49 ms 62968 KB Output is correct
3 Correct 49 ms 63096 KB Output is correct
4 Correct 50 ms 62968 KB Output is correct
5 Correct 49 ms 62968 KB Output is correct
6 Incorrect 85 ms 64508 KB Output isn't correct
7 Halted 0 ms 0 KB -