#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 1e5 + 2;
const ll oo = 1e18;
int n;
ll h[nmax], w[nmax], dp[nmax];
struct segment
{
ll a, b;
segment(ll a = 0, ll b = oo) : a(a), b(b) {}
};
struct node
{
segment line;
node *l, *r;
node(const segment &line = segment(), node *l = nullptr, node *r = nullptr) : line(line), l(l), r(r) {}
};
#define check(x) if (x == nullptr) x = new node()
node *lichao = new node();
ll get(const segment &line, int x)
{
return line.a * x + line.b;
}
void update(node *root, int l, int r, int u, int v, const segment &line)
{
if (l > v || r < u) return;
int mid = l + r >> 1;
if (l >= u && r <= v)
{
check(root -> l);
check(root -> r);
//6 case, lichao min
ll rootL = get(root -> line, l);
ll rootR = get(root -> line, r);
ll rootM = get(root -> line, mid);
ll lineL = get(line, l);
ll lineR = get(line, r);
ll lineM = get(line, mid);
if (rootL <= lineL && rootR <= lineR) return;
if (rootL >= lineL && rootR >= lineR) {root -> line = line; return;}
if (rootL <= lineL && rootM <= lineM)
{
update(root -> r, mid + 1, r, u, v, line);
return;
}
if (rootL >= lineL && rootM >= lineM)
{
update(root -> r, mid + 1, r, u, v, root -> line);
root -> line = line;
return;
}
if (get(root -> line, mid + 1) <= get(line, mid + 1) && rootR <= lineR)
{
update(root -> l, l, mid, u, v, line);
return;
}
if (get(root -> line, mid + 1) >= get(line, mid + 1) && rootR >= lineR)
{
update(root -> l, l, mid, u, v, root -> line);
root -> line = line;
return;
}
}
update(root -> l, l, mid, u, v, line);
update(root -> r, mid + 1, r, u, v, line);
}
void update(int u, int v, const segment &line) {update(lichao, 1, 2e6, 1, 2e6, line);}
ll get(node *root, int l, int r, int x)
{
if (root == nullptr || (l > x || r < x)) return oo;
ll res = get(root -> line, x);
if (l == r) return res;
int mid = l + r >> 1;
res = min(res, get(root -> l, l, mid, x));
res = min(res, get(root -> r, mid + 1, r, x));
return res;
}
int main()
{
if (ifstream(task".inp")) nx
fast
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> h[i];
for (int i = 1; i <= n; ++i)
cin >> w[i];;
dp[1] = -w[1];
update(1, 2e6, segment(-2 * h[1], 1ll * h[1] * h[1] + dp[1]));
for (int i = 2; i <= n; ++i)
{
dp[i] = 1ll * h[i] * h[i] - w[i] + get(lichao, 1, 2e6, h[i]);
update(1, 2e6, segment(-2 * h[i], 1ll * h[i] * h[i] + dp[i]));
}
cout << dp[n] + accumulate(w + 1, w + n + 1, 0LL);
}
Compilation message
building.cpp: In function 'void update(node*, int, int, int, int, const segment&)':
building.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = l + r >> 1;
| ~~^~~
building.cpp: In function 'long long int get(node*, int, int, int)':
building.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int mid = l + r >> 1;
| ~~^~~
building.cpp: In function 'int main()':
building.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:90:31: note: in expansion of macro 'nx'
90 | if (ifstream(task".inp")) nx
| ^~
building.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:90:31: note: in expansion of macro 'nx'
90 | if (ifstream(task".inp")) nx
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2524 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2408 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
4292 KB |
Output is correct |
| 2 |
Correct |
45 ms |
4200 KB |
Output is correct |
| 3 |
Correct |
45 ms |
4200 KB |
Output is correct |
| 4 |
Correct |
51 ms |
3936 KB |
Output is correct |
| 5 |
Incorrect |
49 ms |
7008 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2524 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2408 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
