oj.uz

Submission #699860

# Submission time Handle Problem Language Result Execution time Memory
699860 2023-02-18T07:24:38 Z VietThang Building Bridges (CEOI17_building) C++17
100 / 100
 91 ms 11332 KB 
#include <bits/stdc++.h>

using namespace std;

#define task "BUILD"

#define sz(x) (int)x.size()

const int N = 1e5 + 3;
const long long inf = 1e18;

long long dp[N];
long long pref[N];
int h[N], w[N];
int n;

long long sqr(int x) {
  return 1ll * x * x;
}

namespace sub1 {
  void sol() {
    for (int i = 1; i <= n; i++) dp[i] = inf;
    dp[1] = 0;
//    dp[2] = sqr(h[2] - h[1]);
    for (int i = 2; i <= n; i++) {
      for (int j = i - 1; j >= 1; j--)
        dp[i] = min(dp[i], dp[j] + sqr(h[i] - h[j]) + (pref[i] - pref[j] - w[i]));
    }
    cout << dp[n];
  }
}

long long Res = inf;

namespace sub2 {
  void sol() {
    for (int i = 1; i <= n; i++) dp[i] = inf;
    dp[1] = 0;
    if (n != 1) Res = min(Res, sqr(h[n] - h[1]) + (pref[n] - pref[1] - w[n]));
    for (int i = 2; i <= n; i++) {
      if (i != n) {
          Res = min(Res, sqr(h[i] - h[1]) + sqr(h[i] - h[n])
                + (pref[i] - pref[1] - w[i]) + (pref[n] - pref[i] - w[n]));
      }
      for (int j = i - 1; j >= max(1, i - 1001); j--)
        dp[i] = min(dp[i], dp[j] + sqr(h[i] - h[j]) + (pref[i] - pref[j] - w[i]));
    }
    Res = min(Res, dp[n]);
  }
}

namespace sub3 {
  struct Line {
    bool type;
    double x;
    long long m, c;
  };

  bool operator<(Line l1, Line l2) {
    if (l1.type || l2.type) return l1.x < l2.x;
    return l1.m > l2.m;
  }

  set<Line> cht;

  bool has_prev(set<Line>::iterator it) { return it != cht.begin(); }
  bool has_next(set<Line>::iterator it) {
    return it != cht.end() && next(it) != cht.end();
  }

  double intersect(set<Line>::iterator l1, set<Line>::iterator l2) {
    return (double)(l1->c - l2->c) / (l2->m - l1->m);
  }

  void calc_x(set<Line>::iterator it) {
    if (has_prev(it)) {
      Line l = *it;
      l.x = intersect(prev(it), it);
      cht.insert(cht.erase(it), l);
    }
  }

  bool bad(set<Line>::iterator it) {
    if (has_next(it) && next(it)->c <= it->c) return true;
    return (has_prev(it) && has_next(it) &&
        intersect(prev(it), next(it)) <= intersect(prev(it), it));
  }

  void add_line(long long m, long long c) {
    set<Line>::iterator it;

    it = cht.lower_bound({0, 0, m, c});
    if (it != cht.end() && it->m == m) {
      if (it->c <= c) return;
      cht.erase(it);
    }

    it = cht.insert({0, 0, m, c}).first;
    if (bad(it)) cht.erase(it);
    else {
      while (has_prev(it) && bad(prev(it))) cht.erase(prev(it));
      while (has_next(it) && bad(next(it))) cht.erase(next(it));

      if (has_next(it)) calc_x(next(it));
      calc_x(it);
    }
  }

  long long query(long long h) {
    Line l = *prev(cht.upper_bound({1, (double)h, 0, 0}));
    return l.m * h + l.c;
  }

  void sol() {
    for (int i = 1; i <= n; i++) dp[i] = inf;
    dp[1] = 0;
    add_line(-2 * h[1], -pref[1] + sqr(h[1]));
    for (int i = 2; i <= n; i++) {
      dp[i] = query(h[i]) + sqr(h[i]) + pref[i] - w[i];
      add_line(-2 * h[i], dp[i] - pref[i] + sqr(h[i]));
    }
    Res = min(Res, dp[n]);
  }
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> h[i];
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    pref[i] = pref[i - 1] + w[i];
  }

//  if (n <= 1000) sub1::sol();
//  else {
    Res = inf;
//    sub2::sol();
    sub3::sol();
    cout << Res;
//  }
}

int main() {
//  freopen(task".inp", "r", stdin);
//  freopen(task".out", "w", stdout);
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tc = 1;
//  cin >> tc; cin.ignore();
  while (tc--)
    solve();
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3848 KB Output is correct
2 Correct 70 ms 3768 KB Output is correct
3 Correct 71 ms 3788 KB Output is correct
4 Correct 64 ms 3540 KB Output is correct
5 Correct 61 ms 5048 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 70 ms 3848 KB Output is correct
7 Correct 70 ms 3768 KB Output is correct
8 Correct 71 ms 3788 KB Output is correct
9 Correct 64 ms 3540 KB Output is correct
10 Correct 61 ms 5048 KB Output is correct
11 Correct 60 ms 3788 KB Output is correct
12 Correct 73 ms 3708 KB Output is correct
13 Correct 45 ms 3660 KB Output is correct
14 Correct 66 ms 3864 KB Output is correct
15 Correct 91 ms 11332 KB Output is correct
16 Correct 60 ms 5228 KB Output is correct
17 Correct 21 ms 3644 KB Output is correct
18 Correct 19 ms 3692 KB Output is correct