oj.uz

Submission #582929

# Submission time Handle Problem Language Result Execution time Memory
582929 2022-06-24T15:18:06 Z 600Mihnea Building Bridges (CEOI17_building) C++17
100 / 100
 121 ms 102148 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const ll INF = (ll) 1e18 + 7;

struct T {
  ll a;
  ll b;
  bool mt = 1;

  T() {

  }

  T(ll a, ll b) : a(a), b(b) {
  }

  ll evaluate(ll x) {
    if (mt) {
      return INF;
    }
    return a * x + b;
  }
};

const int N = (int) 1e5 + 7;
const int DIM = (int) 1e6 + 7;
int n;
ll h[N];
ll sum[N];
ll dp[N];
T coef[N];
T tree[4 * DIM];

void addLine(int v, int tl, int tr, T line) {
  if (line.evaluate(tl) <= tree[v].evaluate(tl) && line.evaluate(tr) <= tree[v].evaluate(tr)) {
    tree[v] = line;
    return;
  }
  if (tree[v].evaluate(tl) <= line.evaluate(tl) && tree[v].evaluate(tr) <= line.evaluate(tr)) {
    return;
  }
  assert(tl < tr);
  int tm = (tl + tr) / 2;
  if (line.evaluate(tl) < tree[v].evaluate(tl)) {
    swap(line, tree[v]);
  }
  assert(tree[v].evaluate(tl) <= line.evaluate(tl));
  if (tree[v].evaluate(tm) <= line.evaluate(tm)) {
    addLine(2 * v + 1, tm + 1, tr, line);
  } else {
    swap(line, tree[v]);
    addLine(2 * v, tl, tm, line);
  }
}

ll get(int v, int tl, int tr, int x) {
  if (x < tl || tr < x) {
    return INF;
  }
  ll sol = tree[v].evaluate(x);
  if (tl < tr) {
    int tm = (tl + tr) / 2;
    sol = min(sol, get(2 * v, tl, tm, x));
    sol = min(sol, get(2 * v + 1, tm + 1, tr, x));
  }
  return sol;
}

void addLine(T line) {
  addLine(1, 0, (int) 1e6, line);
}

ll get(int x) {
  return get(1, 0, (int) 1e6, x);
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

 /// freopen ("input.txt", "r", stdin);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    h[i] = x;
  }
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    sum[i] = sum[i - 1] + x;
  }

  dp[1] = 0;
  for (int i = 2; i <= n; i++) {
    dp[i] = INF;
  }

  vector<T> all;

  for (int r = 2; r <= n; r++) {
    T line = {- 2 * h[r - 1], dp[r - 1] + h[r - 1] * h[r - 1] - sum[r - 1]};
    line.mt = 0;

    all.push_back(line);
    addLine(line);

    dp[r] = get(h[r]);

    dp[r] += h[r] * h[r] + sum[r - 1];
  }
  cout << dp[n] << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 96596 KB Output is correct
2 Correct 38 ms 96504 KB Output is correct
3 Correct 36 ms 96572 KB Output is correct
4 Correct 35 ms 96564 KB Output is correct
5 Correct 36 ms 96676 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 102128 KB Output is correct
2 Correct 113 ms 102128 KB Output is correct
3 Correct 92 ms 102036 KB Output is correct
4 Correct 87 ms 102096 KB Output is correct
5 Correct 88 ms 102140 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 96596 KB Output is correct
2 Correct 38 ms 96504 KB Output is correct
3 Correct 36 ms 96572 KB Output is correct
4 Correct 35 ms 96564 KB Output is correct
5 Correct 36 ms 96676 KB Output is correct
6 Correct 97 ms 102128 KB Output is correct
7 Correct 113 ms 102128 KB Output is correct
8 Correct 92 ms 102036 KB Output is correct
9 Correct 87 ms 102096 KB Output is correct
10 Correct 88 ms 102140 KB Output is correct
11 Correct 104 ms 102072 KB Output is correct
12 Correct 93 ms 102096 KB Output is correct
13 Correct 91 ms 102088 KB Output is correct
14 Correct 121 ms 102048 KB Output is correct
15 Correct 87 ms 102080 KB Output is correct
16 Correct 82 ms 102148 KB Output is correct
17 Correct 70 ms 102112 KB Output is correct
18 Correct 69 ms 102052 KB Output is correct