Advertisement
Dang_Quan_10_Tin

BUILDING

Apr 16th, 2022
1,040
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.30 KB | None | 0 0
  1. #define task "BUILDING"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. using ll = long long;
  11. using ld = long double;
  12.  
  13. constexpr int N = 1e5 + 5;
  14. constexpr ll Inf = 1e17;
  15.  
  16. #define sz(x) (int)(x.size())
  17.  
  18. int n;
  19. ll h[N], w[N], dp[N];
  20.  
  21. ll A(int x)
  22. {
  23.     return -2 * h[x];
  24. }
  25.  
  26. ll B(int x)
  27. {
  28.     return dp[x] - w[x] + h[x] * h[x];
  29. }
  30.  
  31. ll More(int x)
  32. {
  33.     return h[x] * h[x] + w[x - 1];
  34. }
  35.  
  36. ld inter(int x, int y)
  37. {
  38.     return (ld)1.0 * (B(x) - B(y)) / (A(y) - A(x));
  39. }
  40.  
  41. struct ConvexHullTrick
  42. {
  43.     vector<int> line;
  44.     vector<ld> point;
  45.     bool Empty;
  46.  
  47.     ConvexHullTrick()
  48.     {
  49.         Empty = 1;
  50.         point.emplace_back(-Inf);
  51.     }
  52.  
  53.     void Clear()
  54.     {
  55.         Empty = 1;
  56.         line.clear();
  57.         point.clear();
  58.         point.emplace_back(-Inf);
  59.     }
  60.  
  61.     void Add(int i)
  62.     {
  63.         while (sz(line) >= 2 || (sz(line) == 1 && A(line[0]) == A(i)))
  64.         {
  65.             if (A(line.back()) != A(i))
  66.             {
  67.                 if (inter(i, line.back()) <= inter(i, line[sz(line) - 2]))
  68.                 {
  69.                     line.pop_back();
  70.                     point.pop_back();
  71.                 }
  72.                 else
  73.                     break;
  74.             }
  75.             else
  76.             {
  77.                 if (B(line.back()) > B(i))
  78.                 {
  79.                     line.pop_back();
  80.                     if (!line.empty())
  81.                         point.pop_back();
  82.                 }
  83.                 else
  84.                     break;
  85.             }
  86.         }
  87.  
  88.         Empty = 0;
  89.  
  90.         if (line.empty() || A(line.back()) != A(i))
  91.         {
  92.             if (!line.empty())
  93.                 point.emplace_back(inter(i, line.back()));
  94.             line.emplace_back(i);
  95.         }
  96.     }
  97.  
  98.     ll Get(int x)
  99.     {
  100.         if (Empty)
  101.             return Inf;
  102.         int j = lower_bound(point.begin(), point.end(), h[x]) - point.begin();
  103.         //cout << line.back() << " " << j - 1 << " " << line[j - 1] << "\n";
  104.         return A(line[j - 1]) * h[x] + B(line[j - 1]) + More(x);
  105.     }
  106. } f[17];
  107.  
  108. void Read()
  109. {
  110.     cin >> n;
  111.     for (int i = 1; i <= n; ++i)
  112.         cin >> h[i];
  113.     for (int i = 1; i <= n; ++i)
  114.     {
  115.         cin >> w[i];
  116.         w[i] += w[i - 1];
  117.     }
  118. }
  119.  
  120. void Update(int x)
  121. {
  122.     int pos = 0;
  123.     vector<int> tmp({x});
  124.  
  125.     while (pos < 17 && !f[pos].Empty)
  126.     {
  127.         for (auto i : f[pos].line)
  128.             tmp.emplace_back(i);
  129.         f[pos].Clear();
  130.         ++pos;
  131.     }
  132.  
  133.     sort(tmp.begin(), tmp.end(), [&](const int &x, const int &y)
  134.          { return A(x) > A(y); });
  135.  
  136.     for (auto i : tmp)
  137.         f[pos].Add(i);
  138. }
  139.  
  140. void Solve()
  141. {
  142.     Update(1);
  143.  
  144.     for (int i = 2; i <= n; ++i)
  145.     {
  146.         dp[i] = Inf;
  147.         for (int j = 0; j < 17; ++j)
  148.             if (!f[j].Empty)
  149.             {
  150.                 //cout << j << " ";
  151.                 dp[i] = min(dp[i], f[j].Get(i));
  152.             }
  153.         Update(i);
  154.         //cout << i << ": " << dp[i] << "\n";
  155.     }
  156.  
  157.     cout << dp[n];
  158. }
  159.  
  160. int32_t main()
  161. {
  162.     ios::sync_with_stdio(0);
  163.     cin.tie(0);
  164.     cout.tie(0);
  165.     if (fopen(task ".INP", "r"))
  166.     {
  167.         freopen(task ".INP", "r", stdin);
  168.         freopen(task ".OUT", "w", stdout);
  169.     }
  170.     Read();
  171.     Solve();
  172. }
  173.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement