#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
struct line_t {
bool t;
long long in;
int a; long long b;
line_t(bool _t = 0, long long _in = 0, int _m = 0, long long _c = 0) : t(_t), in(_in), a(_m), b(_c) {}
long long f(int x) {
return 1LL * a * x + b;
}
bool operator < (const line_t &oth) const {
if (t || oth.t) {
return in < oth.in;
}
return a > oth.a;
}
};
struct ConvexHullTrick {
set<line_t> lns;
long long cdiv(long long a, long long b) {
return a / b - ((a ^ b) < 0 && a % b);
}
long long inter(line_t ln1, line_t ln2) {
return cdiv(ln1.b - ln2.b, ln2.a - ln1.a);
}
bool is_keep(set<line_t>::iterator it) {
if (it == lns.begin() || next(it) == lns.end()) {
return true;
}
return inter(*prev(it), *it) <= inter(*prev(it), *next(it));
}
void upd(set<line_t>::iterator it) {
if (it == lns.begin()) {
return;
}
line_t tmp = *it;
tmp.in = inter(*prev(it), *it);
lns.insert(lns.erase(it), tmp);
}
void add(int a, long long b) {
auto it = lns.lower_bound(line_t(0, 0, a, b));
if (it != lns.end() && it -> a == a) {
if (it -> b <= b) {
return;
}
lns.erase(it);
}
lns.insert(line_t(0, 0, a, b));
it = lns.lower_bound(line_t(0, 0, a, b));
if (!is_keep(it)) {
lns.erase(it);
return;
}
while (it != lns.begin() && !is_keep(prev(it))) {
lns.erase(prev(it));
}
while (it != lns.end() && next(it) != lns.end() && !is_keep(next(it))) {
lns.erase(next(it));
}
if (it != lns.end() && next(it) != lns.end()) {
upd(next(it));
}
upd(it);
}
long long get(int x) {
assert(lns.size() > 0);
line_t res = *prev(lns.upper_bound(line_t(1, x, 0, 0)));
return res.f(x);
}
} cht;
const int N = 1e5 + 7;
int n;
int a[N];
long long dp[N];
long long pref[N];
signed main()
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
for (int i = 1; i <= n; i ++) {
int x; cin >> x;
pref[i] = pref[i - 1] + x;
}
#define SQR(x) 1LL * (x) * (x)
for (int i = 2; i <= n; i ++) {
cht.add(-2 * a[i - 1], dp[i - 1] + SQR(a[i - 1]) - pref[i - 1]);
dp[i] = cht.get(a[i]) + SQR(a[i]) + pref[i - 1];
}
cout << dp[n];
return 0;
}
Compilation message
building.cpp:101:3: error: expected initializer before 'cin'
101 | cin.tie(0)->sync_with_stdio(0);
| ^~~
building.cpp:102:3: error: 'cin' does not name a type; did you mean 'sin'?
102 | cin >> n;
| ^~~
| sin
building.cpp:103:3: error: expected unqualified-id before 'for'
103 | for (int i = 1; i <= n; i ++) {
| ^~~
building.cpp:103:19: error: 'i' does not name a type
103 | for (int i = 1; i <= n; i ++) {
| ^
building.cpp:103:27: error: 'i' does not name a type
103 | for (int i = 1; i <= n; i ++) {
| ^
building.cpp:106:3: error: expected unqualified-id before 'for'
106 | for (int i = 1; i <= n; i ++) {
| ^~~
building.cpp:106:19: error: 'i' does not name a type
106 | for (int i = 1; i <= n; i ++) {
| ^
building.cpp:106:27: error: 'i' does not name a type
106 | for (int i = 1; i <= n; i ++) {
| ^
building.cpp:111:3: error: expected unqualified-id before 'for'
111 | for (int i = 2; i <= n; i ++) {
| ^~~
building.cpp:111:19: error: 'i' does not name a type
111 | for (int i = 2; i <= n; i ++) {
| ^
building.cpp:111:27: error: 'i' does not name a type
111 | for (int i = 2; i <= n; i ++) {
| ^
building.cpp:115:3: error: 'cout' does not name a type
115 | cout << dp[n];
| ^~~~
building.cpp:116:3: error: expected unqualified-id before 'return'
116 | return 0;
| ^~~~~~
building.cpp:117:1: error: expected declaration before '}' token
117 | }
| ^
