//Make CSP great again
//You're as beautiful as the day I lost you
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 2e5;
long long dp[N + 1], h[N + 1], w[N + 1], s = 0;
int n;
long long A(int i)
{
return -2 * h[i];
}
long long B(int j)
{
return dp[j] + h[j] * h[j];
}
long long C(int i)
{
return h[i] * h[i] - w[i];
}
struct CHT
{
bool Empty = true;
vector<long double> Point;
vector<int> Line;
void Clear()
{
Point.clear();
Line.clear();
Empty = true;
}
long double Intersect(int i, int j)
{
return (long double)(B(j) - B(i))/(A(i) - A(j));
}
bool ok(int i)
{
return Intersect(i, Line.back()) > Intersect(i, Line[Line.size() - 2]);
}
void Add(int i)
{
Empty = false;
while (Line.size() > 1 || (Line.size() == 1 && A(i) == A(Line.back())))
{
if (A(i) == A(Line.back()))
{
if (B(i) < B(Line.back()))
{
Line.pop_back();
Point.pop_back();
}
else
{
break ;
}
}
else if (!ok(i))
{
Line.pop_back();
Point.pop_back();
}
else
{
break;
}
}
if (Line.empty())
{
Point.push_back(-1e18);
}
else
{
Point.push_back(Intersect(i, Line.back()));
}
Line.push_back(i);
}
long long Get(int i)
{
int j = upper_bound(Point.begin(), Point.end(), (long double)(h[i])) - Point.begin() - 1;
return A(Line[j]) * h[i] + B(Line[j]) + C(i);
}
};
CHT f[17];
void read()
{
cin >> n;
for (int i = 1; i <= n; ++ i)
{
cin >> h[i];
}
for (int i = 1; i <= n; ++ i)
{
cin >> w[i];
s += w[i];
}
}
void Update(int i)
{
int pos = 0;
vector<int> tmp = {i};
while (pos < 17 && !f[pos].Empty)
{
for (int j : f[pos].Line)
{
tmp.push_back(j);
}
f[pos].Clear();
++pos;
}
sort(tmp.begin(), tmp.end(), [](int x, int y)
{
return A(x) > A(y);
});
for (int j : tmp)
{
f[pos].Add(j);
}
}
void solve()
{
dp[1] = -w[1];
for (int i = 2; i <= n; ++ i)
{
dp[i] = 1e9;
Update(i - 1);
for (int j = 0; j < 17; ++ j)
{
if (!f[j].Empty)
{
dp[i] = min(dp[i], f[j].Get(i));
}
}
}
cout << dp[n] + s;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}
Compilation message
building.cpp: In function 'int main()':
building.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
4020 KB |
Output is correct |
| 2 |
Correct |
118 ms |
4004 KB |
Output is correct |
| 3 |
Correct |
110 ms |
4004 KB |
Output is correct |
| 4 |
Correct |
105 ms |
3644 KB |
Output is correct |
| 5 |
Incorrect |
78 ms |
4660 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
