/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/CEOI17_building
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
#define adjread {int a, b; cin >> a >> b; adjlist[a].pb(b); adjlist[b].pb(a); }
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
bool debug;
int N;
ll h[MAXV], w[MAXV], psw[MAXV];
ll dp[MAXV];
/**
* Author: Simon Lindholm
* Date: 2017-04-20
* License: CC0
* Source: own work
* Description: Container where you can add lines of the form kx+m, and query maximum values at points x.
* lower convext hull
* Useful for dynamic programming (``convex hull trick'').
* Time: O(\log N)
* Status: stress-tested
* https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LineContainer.h
* usage example: https://oj.uz/submission/237141
*/
#include <assert.h> /* assert */
int lc_comp_type = 1;
struct Line {
/// y = kx + m; p is the intersection point of line y and the next line on the convex hull
mutable ll k, m, p; // can add additional info such as id
bool operator<(const Line& o) const {
if(lc_comp_type == 1) {
return k < o.k;
} else {
return p < o.p;
}
}
//bool operator<(const ll& x) const { return p < x; }
};
struct LineContainer {
multiset<Line> hull;
int hull_type = 1; /// 1 for max val (lower convex hull), -1 for min val (upper convex hull)
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll lc_inf = 1LL << 62;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(multiset<Line>::iterator x, multiset<Line>::iterator y) {
if (y == hull.end()) { x->p = lc_inf; return false; }
if (x->k == y->k) x->p = (x->m > y->m) ? lc_inf : -lc_inf;
else x->p = div(y->m - x->m, x->k - y->k); // p is the intersect against next line
return x->p >= y->p;
}
void add(ll k, ll m) {
/// if, instead of max val (lower convex hull), we need min val (upper convex hull), we flip the hull
k *= (ll)hull_type; m *= (ll)hull_type;
auto z = hull.insert({k, m, 0}), y = z, x = y;
z++;
while (isect(y, z)) z = hull.erase(z);
if (x != hull.begin() && isect(--x, y)) isect(x, y = hull.erase(y));
while ((y = x) != hull.begin() && (--x)->p >= y->p)
isect(x, hull.erase(y));
}
ll query(ll x) {
assert(!hull.empty());
Line ql; ql.p = x;
lc_comp_type = 2;
auto l = *hull.lower_bound(ql);
lc_comp_type = 1;
return (l.k * x + l.m) * (ll)hull_type;
}
};
Line l;
LineContainer lc;
int main() {
debug = false;
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N ;
for(int i=1;i<=N;i++) {
cin >> h[i];
}
for(int i=1;i<=N;i++) {
cin >> w[i];
psw[i] = psw[i-1] + w[i];
}
lc.hull_type = -1;
dp[1] = 0;
lc.add(-2LL*h[1], dp[1]-psw[1]+h[1]*h[1]);
for(int i=2;i<=N;i++) {
dp[i] = lc.query(h[i]) + h[i] * h[i] + psw[i-1];
if(debug) cout << dp[i] << endl;
lc.add(-2LL*h[i], dp[i]-psw[i]+h[i]*h[i]);
}
cout << dp[N] << endl;
if(debug) cout << endl << "EOL" << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
49 ms |
4472 KB |
Output is correct |
| 3 |
Correct |
48 ms |
4544 KB |
Output is correct |
| 4 |
Correct |
46 ms |
4412 KB |
Output is correct |
| 5 |
Correct |
42 ms |
5512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
48 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
49 ms |
4472 KB |
Output is correct |
| 8 |
Correct |
48 ms |
4544 KB |
Output is correct |
| 9 |
Correct |
46 ms |
4412 KB |
Output is correct |
| 10 |
Correct |
42 ms |
5512 KB |
Output is correct |
| 11 |
Correct |
46 ms |
4680 KB |
Output is correct |
| 12 |
Correct |
49 ms |
4416 KB |
Output is correct |
| 13 |
Correct |
36 ms |
4532 KB |
Output is correct |
| 14 |
Correct |
54 ms |
4656 KB |
Output is correct |
| 15 |
Correct |
62 ms |
10452 KB |
Output is correct |
| 16 |
Correct |
40 ms |
5540 KB |
Output is correct |
| 17 |
Correct |
26 ms |
4420 KB |
Output is correct |
| 18 |
Correct |
26 ms |
4420 KB |
Output is correct |
