oj.uz

Submission #593728

# Submission time Handle Problem Language Result Execution time Memory
593728 2022-07-11T14:09:06 Z cadmiumsky Building Bridges (CEOI17_building) C++14
100 / 100
 127 ms 66452 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll nmax = 1e5 + 5, hmax = 1e6 + 1, inf = 1e9 + 5;

struct func {
  ll m = inf, b = 1e15 + 5;
  func(ll a = inf, ll c = 1e15 + 5): m(a), b(c) {;} 
  ll operator()(const ll &x) const {
    return m * x + b;
  }
  bool operator == (const func& other) { return other.m == m && other.b == b; }
};

namespace LiChao {
  func aint[hmax * 4];
  void push(func x, int node = 1, int cl = 0, int cr = hmax) {
    int mid = cl + cr >> 1;
    bool md = x(mid) < aint[node](mid), rh = x(cr) < aint[node](cr);
    if(md)
      swap(aint[node], x);
    if(cl == cr)
      return;
    if(rh != md)
      push(x, 2 * node + 1, mid + 1, cr);
    else
      push(x, 2 * node, cl, mid);
    return;
  }
  ll query(int poz, int node = 1, int cl = 0, int cr = hmax) {
    if(cl == cr)
      return aint[node](poz);
    int mid = cl + cr >> 1;
    if(poz <= mid)
      return min(aint[node](poz), query(poz, 2 * node, cl, mid));
    return min(aint[node](poz), query(poz, 2 * node + 1, mid + 1, cr));
  }
};

ll h[nmax], w[nmax], dp[nmax];
ll p2(ll x) {return x * x;}


int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> h[i];
  for(int i = 1; i <= n; i++)
    cin >> w[i],
    w[i] += w[i - 1];
  
  dp[1] = 0;
  LiChao::push(func(-h[1] * 2, -w[1] + p2(h[1]) + dp[1]));
  
  ll rez = 0;
  for(int i = 2; i <= n; i++) {
    dp[i] = LiChao::query(h[i]) + w[i - 1] + p2(h[i]);
    //cerr << LiChao::query(h[i]) << ' ' << dp[i] << ' ';
    LiChao::push(func(-h[i] * 2, -w[i] + p2(h[i]) + dp[i])); 
  }
  cout << dp[n] << '\n';
}

Compilation message

building.cpp: In function 'void LiChao::push(func, int, int, int)':
building.cpp:19:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
building.cpp: In function 'll LiChao::query(int, int, int, int)':
building.cpp:34:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
building.cpp: In function 'int main()':
building.cpp:57:6: warning: unused variable 'rez' [-Wunused-variable]
   57 |   ll rez = 0;
      |      ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 25 ms 62932 KB Output is correct
3 Correct 26 ms 62916 KB Output is correct
4 Correct 26 ms 62832 KB Output is correct
5 Correct 27 ms 62888 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 65228 KB Output is correct
2 Correct 92 ms 65216 KB Output is correct
3 Correct 97 ms 65148 KB Output is correct
4 Correct 87 ms 65232 KB Output is correct
5 Correct 96 ms 65228 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 25 ms 62932 KB Output is correct
3 Correct 26 ms 62916 KB Output is correct
4 Correct 26 ms 62832 KB Output is correct
5 Correct 27 ms 62888 KB Output is correct
6 Correct 92 ms 65228 KB Output is correct
7 Correct 92 ms 65216 KB Output is correct
8 Correct 97 ms 65148 KB Output is correct
9 Correct 87 ms 65232 KB Output is correct
10 Correct 96 ms 65228 KB Output is correct
11 Correct 119 ms 66452 KB Output is correct
12 Correct 123 ms 66260 KB Output is correct
13 Correct 92 ms 66248 KB Output is correct
14 Correct 127 ms 66448 KB Output is correct
15 Correct 89 ms 66056 KB Output is correct
16 Correct 92 ms 66136 KB Output is correct
17 Correct 93 ms 66304 KB Output is correct
18 Correct 108 ms 66316 KB Output is correct