// Goten2308
#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using ii = pair <int, int>;
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define BIT(x, y) ((x >> y) & 1)
#define MASK(x) (1 << x)
#define MOD 1000000007
#define MULTI_TEST1
template <class T> bool maximize(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template <class T> bool minimize(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template <class T> void add(T& a, T b) { a += b; if(a >= MOD) a -= MOD; }
template <class T> void sub(T& a, T b) { a -= b; if(a <= 0) a += MOD; }
const int maxN = (int)1e5 + 7, maxVal = (int)1e6 + 7, maxLog = 63 - __builtin_clzll(maxN) + 2, INF = (int)1e17 + 7;
int val[maxVal];
vector<int> comp;
struct Line {
ll a, b;
Line() {
a = INF;
b = INF;
}
Line(ll _a, ll _b) {
a = _a;
b = _b;
}
ll operator() (ll x) {
return a * x + b;
}
} node[MASK(maxLog)];
void ins(int id, int l, int r, Line L) {
if(l > r) return;
if(l == r) {
node[id] = L;
return;
}
int m = (l + r) >> 1;
if(node[id].a > L.a) swap(node[id], L);
if(node[id](val[m]) > L(val[m])) {
swap(node[id], L);
ins(id << 1 | 1, m + 1, r, L);
}else ins(id << 1, l, m, L);
}
void ins(Line L) {
ins(1, 1, comp.size(), L);
}
ll get(int id, int l, int r, int x) {
if(l > r) return INF;
if(l == r) return node[id](val[x]);
int m = (l + r) >> 1;
if(x <= m) return min(node[id](val[x]), get(id << 1, l, m, x));
return min(node[id](val[x]), get(id << 1 | 1, m + 1, r, x));
}
ll get(int x) {
return get(1, 1, comp.size(), x);
}
int n, h[maxN], w[maxN], f[maxN], psW[maxN];
#define sqr(x) (x * x)
void solve() {
cin >> n;
vector<int> V(n + 1);
for (int i = 1; i <= n; i++) {
cin >> h[i];
comp.pb(h[i]);
}
for (int i = 1; i <= n; i++) cin >> w[i];
sort(all(comp));
comp.resize(unique(all(comp)) - comp.begin());
for(int i = 1; i <= n; i++) {
h[i] = lower_bound(all(comp), h[i]) - comp.begin() + 1;
val[h[i]] = comp[h[i] - 1];
V[i] = comp[h[i] - 1];
}
f[1] = 0;
for (int i = 1; i <= n; i++) {
psW[i] = psW[i - 1] + w[i];
}
ins(Line(-2 * V[1], 0 - psW[1] + sqr(V[1]))); // ax + b
for(int i = 2; i <= n; i++) {
f[i] = get(h[i]) + sqr(V[i]) + psW[i - 1];
ins(Line(-2 * V[i], f[i] - psW[i] + sqr(V[i])));
}
cout << f[n] << endl;
}
signed main(){
#define task ""
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
if(fopen("task.inp", "r")){
freopen("task.inp", "r", stdin);
//freopen("task.out", "w", stdout);
}
cin.tie(0)->ios_base::sync_with_stdio(0);
int nTest = 1;
#ifdef MULTI_TEST
cin >> nTest;
#endif
while(nTest--) {
solve();
}
return 0;
}
Compilation message
building.cpp: In function 'int main()':
building.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | freopen("task.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
10456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
