oj.uz

Submission #593717

# Submission time Handle Problem Language Result Execution time Memory
593717 2022-07-11T13:59:14 Z cadmiumsky Building Bridges (CEOI17_building) C++14
30 / 100
 111 ms 65228 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 = inf;
  func(ll a = inf, ll c = inf): 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 = 1, 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 || aint[node] == x)
      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 = 1, 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]);
    //cout << 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 32 ms 62816 KB Output is correct
2 Correct 27 ms 62808 KB Output is correct
3 Correct 29 ms 62940 KB Output is correct
4 Correct 32 ms 62860 KB Output is correct
5 Correct 31 ms 62884 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 65228 KB Output is correct
2 Correct 105 ms 65136 KB Output is correct
3 Correct 111 ms 65180 KB Output is correct
4 Correct 105 ms 65184 KB Output is correct
5 Incorrect 90 ms 65176 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62816 KB Output is correct
2 Correct 27 ms 62808 KB Output is correct
3 Correct 29 ms 62940 KB Output is correct
4 Correct 32 ms 62860 KB Output is correct
5 Correct 31 ms 62884 KB Output is correct
6 Correct 100 ms 65228 KB Output is correct
7 Correct 105 ms 65136 KB Output is correct
8 Correct 111 ms 65180 KB Output is correct
9 Correct 105 ms 65184 KB Output is correct
10 Incorrect 90 ms 65176 KB Output isn't correct
11 Halted 0 ms 0 KB -