Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 100005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- typedef int ftype;
- typedef complex<ftype> point;
- const int inf = 1e10;
- const int minf = -1e10;
- #define x real
- #define y imag
- vector<point> hull, vecs;
- ftype cross(point a, point b){
- return (conj(a)*b).imag();
- }
- ftype dot(point a, point b){
- return (conj(a)*b).real();
- }
- void add_line(ftype k, ftype b){
- point nw = {k,b};
- //dot > 0 -> k giam dan
- //dot < 0 -> k tang dan
- while (vecs.size() && dot(vecs.back(),(nw-hull.back()))>0){
- vecs.pop_back();
- hull.pop_back();
- }
- if (hull.size()){
- vecs.push_back(point(1i)*(nw-hull.back()));
- }
- hull.push_back(nw);
- }
- ftype get(ftype x){
- point q = {x,1};
- auto it = lower_bound(vecs.begin(),vecs.end(),q,
- [](point a, point b){
- return cross(a,b)>0;
- });
- //min cross > 0
- //max cross < 0
- return dot(q,hull[it-vecs.begin()]);
- }
- int n,c;
- int dp[N], a[N], b[N];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n >> c;
- for(int i=1; i<=n; i++) cin >> a[i];
- for(int i=1; i<=n; i++) cin >> b[i];
- }
- void proc()
- {
- dp[1] = c;
- add_line(b[1],dp[1]);
- int Min = dp[1];
- for(int i=2; i<=n; i++){
- dp[i] = get(a[i]);
- if (b[i]<b[i-1] || (b[i]==b[i-1] && dp[i]<Min)) add_line(b[i],dp[i]);
- }
- cout << dp[n];
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement