This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
// gives the number of keys with value strictly less than x
#define lesscount(x) order_of_key(x)
// gives the iterator to kth element (starting from 0)
#define kthiterator(x) find_by_order(x)
#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define readfile(s) freopen(s, "r", stdin)
#define writefile(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define cin_cout_is_cool ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PrintBinary(n) cout << #n << " = " << bitset<64>(n) << endl
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define cin(n) scanf("%d", &n)
#define popcount(x) __builtin_popcount((x))
#define popcountll(x) __builtin_popcountll((x))
inline int myrand(int l, int r) {
int ret = rand(); ret <<= 15; ret ^= rand();
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
return os<<"(" <<p.first<<", "<<p.second<<")"; }
typedef pair<int, int> ii;
template<typename T> using min_pq =
priority_queue<T, vector<T>, greater<T> >;
template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_, T d_) { return min(min(a_, b_),min(c_,d_)); }
template<typename T>T max(T a_,T b_,T c_, T d_) { return max(max(a_, b_),max(c_,d_)); }
//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};
template<typename T> inline T ceil(T num, T d)
{ return (T)(num/d) + (num%d>(T)0 ? (T)1 : (T)0); }
#define block_no(idx) (idx/BLOCK_SIZE)
#define block_starting(idx) (block_no(idx)*BLOCK_SIZE)
#define block_ending(idx) (min(n, block_no(idx)*BLOCK_SIZE+BLOCK_SIZE-1))
#define block_rank(idx) (idx%BLOCK_SIZE)
#define int long long
typedef long long ll;
// does everything for maximums
const ll is_query = LLONG_MIN+1LL;
struct Line {
ll m, b;
mutable function<const Line*()> succ;
bool operator<(const Line& rhs) const {
if (rhs.b != is_query) return m < rhs.m;
const Line* s = succ();
if (!s) return 0;
ll x = rhs.m;
return b - s->b < (s->m - m) * x;
}
};
struct HullDynamic : public multiset<Line> { // will maintain lower hull for maximum
bool bad(iterator y) {
auto z = next(y);
if (y == begin()) {
if (z == end()) return 0;
return y->m == z->m && y->b <= z->b;
}
auto x = prev(y);
if (z == end()) return y->m == x->m && y->b <= x->b;
return 1.0*(x->b - y->b)*(z->m - y->m) >= 1.0*(y->b - z->b)*(y->m - x->m);
}
void addline(ll m, ll b) {
auto y = insert({ -m, -b }); // edit here for minimumns
y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
if (bad(y)) { erase(y); return; }
while (next(y) != end() && bad(next(y))) erase(next(y));
while (y != begin() && bad(prev(y))) erase(prev(y));
}
ll query(ll x) {
auto l = *lower_bound((Line) { x, is_query });
return -(l.m * x + l.b); // edit here for minimums
}
}cht;
const int maxn = 100010;
int n, pre[maxn], h[maxn], dp[maxn];
inline int sq(int x) {
return x * x;
}
int32_t main () {
//readfile("input.in");
//writefile("output.out");
cin>>n;
for(int i=1; i<=n; i++) cin>>h[i];
for(int i=1; i<=n; i++) cin>>pre[i];
for(int i=1; i<=n; i++) pre[i] += pre[i-1];
dp[1] = 0;
for(int i=2; i<=n; i++) {
cht.addline(-2*h[i-1], sq(h[i-1])+dp[i-1]-pre[i-1]);
dp[i] = cht.query(h[i])+pre[i-1]+sq(h[i]);
}
cout<<dp[n]<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |