fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int N = 2e5 + 5;
  5.  
  6. struct Line {
  7.   ll a, b;
  8.   ll calc(ll x) {
  9.     return a * x + b;
  10.   }
  11. };
  12.  
  13. int n, seen;
  14. ll s[N], f[N], dp[N];
  15. vector<Line> A;
  16.  
  17. bool overlap(const Line &p1, const Line &p2, const Line &p3) {
  18.   return (p3.b - p1.b) * (p1.a - p2.a) <= (p2.b - p1.b) * (p1.a - p3.a);
  19. }
  20.  
  21. void add_line(ll a, ll b) {
  22.   Line new_line = {a, b};
  23.   while ((int)A.size() > seen + 1 && overlap(A[(int)A.size() - 2], A.back(), new_line)) A.pop_back();
  24.   A.push_back(new_line);
  25. }
  26.  
  27. ll query(ll x) {
  28.   while (seen + 1 < (int)A.size() && A[seen].calc(x) >= A[seen + 1].calc(x)) ++seen;
  29.   return A[seen].calc(x);
  30. }
  31.  
  32. int main() {
  33.   ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  34.   cin >> n >> f[0];
  35.   for (int i = 1; i <= n; ++i) {
  36.     cin >> s[i];
  37.   }
  38.   add_line(f[0], dp[0]);
  39.   for (int i = 1; i <= n; ++i) {
  40.     cin >> f[i];
  41.     dp[i] = query(s[i]);
  42.     add_line(f[i], dp[i]);
  43.   }
  44.   cout << dp[n];
  45.   return 0;
  46. }
  47.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/lml4Ft
language:
C++14 (gcc 8.3)
created:
179 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!