oj.uz

Submission #697964

# Submission time Handle Problem Language Result Execution time Memory
697964 2023-02-11T15:33:37 Z dattranxxx Building Bridges (CEOI17_building) C++11
100 / 100
 90 ms 66628 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 5;
const ll INF = 1e12;
const ll LLINF = 1e18;
ll h[N], w[N];
int n;

ll dp[N];

ll sqr(ll x) {
  return x * x;
}

namespace task1 {
  void solve() {
    dp[1] = 0;
    for (int i = 2; i <= n; ++i) {
      dp[i] = LLINF;
      for (int j = i - 1; j; --j) {
        dp[i] = min(dp[i], dp[j] + sqr(h[i] - h[j]) + (w[i - 1] - w[j]));
      }
    }
    cout << dp[n];
  }
}

namespace task2 {
  const int C = 1e6;
  
  struct Line {
    ll a, b;
    Line(ll a = INF, ll b = INF): a(a), b(b) {}
    ll get(ll x) {
      return a * x + b;
    }
  };
  
  struct LichaoTree {
    // vector<Line> cont;
    // void update(ll a, ll b) {
      // cont.emplace_back(a, b);
    // }
//     
    // ll get(ll x) {
      // ll res = INF;
      // for (auto& l : cont)
        // res = min(res, l.get(x));
      // return res;
    // }
    Line v; ll x, res;
    Line lct[(C + 1) * 4];
    void update(int i, int l, int r) {
      if (l == r) 
        return lct[i] = v.get(l) < lct[i].get(l) ? v : lct[i], void();
      int m = (l + r) / 2;
      if (v.a > lct[i].a) swap(v, lct[i]);
      if (v.get(m) < lct[i].get(m)) {
        swap(v, lct[i]);
        update(i * 2, l, m);
      } else {
        update(i * 2 + 1, m + 1, r);
      }
    }
    
    void get(int i, int l, int r) {
      res = min(res, lct[i].get(x));
      if (l == r) return;
      int m = (l + r) / 2;
      if (x <= m) get(i * 2, l, m);
      else get(i * 2 + 1, m + 1, r);
    }
    
    void update(ll a, ll b) {
      v = Line(a, b);
      update(1, 0, C);
    }
    
    ll get(ll x) {
      res = LLINF;
      this->x = x;
      get(1, 0, C);
      return res;
    }
    
  } lct;
  
  void solve() {
    dp[1] = 0;
    lct.update(-2 * h[1], dp[1] + sqr(h[1]) - w[1]);
    for (int i = 2; i <= n; ++i) {
      // dp[i] = h[i]^2 + w[i-1] + MIN[(-2h[j]) * h[i] + dp[j] + h[j]^2 - w[j]]
      dp[i] = sqr(h[i]) + w[i-1] + lct.get(h[i]);
      lct.update(-2 * h[i], dp[i] + sqr(h[i]) - w[i]);
    }
    cout << dp[n];
  }
}


int main() {
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  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];
    
  if (n <= 1000) task1::solve();
  else task2::solve();
  
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 27 ms 62900 KB Output is correct
3 Correct 25 ms 62848 KB Output is correct
4 Correct 26 ms 62976 KB Output is correct
5 Correct 26 ms 62884 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 65228 KB Output is correct
2 Correct 65 ms 65148 KB Output is correct
3 Correct 66 ms 65272 KB Output is correct
4 Correct 82 ms 65256 KB Output is correct
5 Correct 55 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 27 ms 62900 KB Output is correct
3 Correct 25 ms 62848 KB Output is correct
4 Correct 26 ms 62976 KB Output is correct
5 Correct 26 ms 62884 KB Output is correct
6 Correct 66 ms 65228 KB Output is correct
7 Correct 65 ms 65148 KB Output is correct
8 Correct 66 ms 65272 KB Output is correct
9 Correct 82 ms 65256 KB Output is correct
10 Correct 55 ms 65228 KB Output is correct
11 Correct 73 ms 66480 KB Output is correct
12 Correct 90 ms 66276 KB Output is correct
13 Correct 71 ms 66380 KB Output is correct
14 Correct 82 ms 66628 KB Output is correct
15 Correct 59 ms 66124 KB Output is correct
16 Correct 57 ms 66164 KB Output is correct
17 Correct 52 ms 66280 KB Output is correct
18 Correct 52 ms 66344 KB Output is correct