#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#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;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const double PI = 4 * atan(1);
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>
#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)
void fast_io(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
}
void io(string taskname){
string fin = taskname + ".in";
string fout = taskname + ".out";
const char* FIN = fin.c_str();
const char* FOUT = fout.c_str();
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
fast_io();
}
const int MAX = 1e5 + 5;
vector<ll> h;
vector<ll> w;
ll pre[MAX];
ll dp[MAX];
#define MAXLC 1000000000
#define INF (1LL<<60)
inline long long f(long long m, long long b, int x) {
return m * x + b;
}
struct lc_node {
long long m = 0, b = INF;
lc_node *l = nullptr, *r = nullptr;
~lc_node() { delete l; delete r; }
void add_line(long long nm, long long nb, int lo=0, int hi=MAXLC) {
int mid = (lo + hi) / 2;
bool bl = f(nm, nb, lo) < f(m, b, lo);
bool bm = f(nm, nb, mid) < f(m, b, mid);
bool bh = f(nm, nb, hi) < f(m, b, hi);
if (bm) {
swap(nm, m);
swap(nb, b);
}
if (lo == hi || nb == INF)
return;
else if (bl != bm) {
if (!l) l = new lc_node;
l->add_line(nm, nb, lo, mid - 1);
}
else if (bh != bm) {
if (!r) r = new lc_node;
r->add_line(nm, nb, mid + 1, hi);
}
}
long long get(int x, int lo=0, int hi=MAXLC) {
int mid = (lo + hi) / 2;
long long ret = f(m, b, x);
if (l && x < mid)
ret = min(ret, l->get(x, lo, mid - 1));
if (r && x > mid)
ret = min(ret, r->get(x, mid + 1, hi));
return ret;
}
void clear() {
delete l; delete r;
m = 0, b = INF, l = nullptr, r = nullptr;
}
} lc;
int main(){
fast_io();
int n;
cin >> n;
f0r(i, n){
int hi;
cin >> hi;
h.eb(hi);
}
f0r(i, n){
int wi;
cin >> wi;
w.eb(wi);
if(i == 0) pre[i] = wi;
else pre[i] = pre[i-1] + wi;
}
f0r(i, n){
if(i == 0){
lc.add_line(-2*h[i], dp[i] + h[i]*h[i] - pre[i]);
}
else{
dp[i] = lc.get(h[i]) + h[i]*h[i] + pre[i-1];
lc.add_line(-2*h[i], dp[i] - pre[i] + h[i]*h[i]);
}
}
cout << dp[n-1] << endl;
return 0;
}
Compilation message
building.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
building.cpp: In function 'void io(std::__cxx11::string)':
building.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FIN, "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~
building.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FOUT, "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
5000 KB |
Output is correct |
| 2 |
Correct |
73 ms |
4848 KB |
Output is correct |
| 3 |
Correct |
70 ms |
4740 KB |
Output is correct |
| 4 |
Correct |
68 ms |
4588 KB |
Output is correct |
| 5 |
Correct |
55 ms |
5996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
3 ms |
376 KB |
Output is correct |
| 6 |
Correct |
74 ms |
5000 KB |
Output is correct |
| 7 |
Correct |
73 ms |
4848 KB |
Output is correct |
| 8 |
Correct |
70 ms |
4740 KB |
Output is correct |
| 9 |
Correct |
68 ms |
4588 KB |
Output is correct |
| 10 |
Correct |
55 ms |
5996 KB |
Output is correct |
| 11 |
Correct |
65 ms |
4784 KB |
Output is correct |
| 12 |
Correct |
68 ms |
4764 KB |
Output is correct |
| 13 |
Correct |
56 ms |
4708 KB |
Output is correct |
| 14 |
Correct |
67 ms |
4968 KB |
Output is correct |
| 15 |
Correct |
62 ms |
9084 KB |
Output is correct |
| 16 |
Correct |
56 ms |
5972 KB |
Output is correct |
| 17 |
Correct |
27 ms |
4716 KB |
Output is correct |
| 18 |
Correct |
26 ms |
4716 KB |
Output is correct |
