oj.uz

Submission #554993

# Submission time Handle Problem Language Result Execution time Memory
554993 2022-04-29T19:39:25 Z MilosMilutinovic Building Bridges (CEOI17_building) C++14
100 / 100
 85 ms 66476 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  vector<int> w(n);
  for (int i = 0; i < n; i++) {
    cin >> w[i];
  }
  vector<long long> pref(n);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      pref[i] = pref[i - 1];
    }
    pref[i] += w[i];
  }
  const int MAX = 1e6 + 5;
  vector<pair<long long, long long>> st(4 * MAX, {-1, -1});
  function<void(int, int, int, pair<long long, long long>)> modify = [&](int node, int l, int r, pair<long long, long long> line) {
    if (st[node].first == -1) {
      st[node] = line;
      return;
    }
    long long a = st[node].first * l + st[node].second;
    long long b = line.first * l + line.second;
    long long c = st[node].first * r + st[node].second;
    long long d = line.first * r + line.second;
    if (a >= b && c >= d) return;
    if (a <= b && c <= d) {
      st[node] = line;
      return;
    }
    int mid = l + r >> 1;
    if (a < b) {
      swap(st[node], line);
    }
    if (st[node].first * mid + st[node].second >= line.first * mid + line.second) {
      modify(node + node + 1, mid + 1, r, line);
    } else {
      swap(st[node], line);
      modify(node + node, l, mid, line);
    }
  };
  function<long long(int, int, int, int)> query = [&](int node, int l, int r, int i) {
    if (st[node].second == -1) {
      return (long long) -1e18;
    }
    if (l == r) {
      return st[node].first * i + st[node].second;
    }
    int mid = l + r >> 1;
    long long val = st[node].first * i + st[node].second;
    if (i <= mid) {
      val = max(val, query(node + node, l, mid, i));
    } else {
      val = max(val, query(node + node + 1, mid + 1, r, i));
    }
    return val;
  };
  modify(1, 0, MAX, {2 * h[0], -h[0] * 1LL * h[0] + w[0]});
  vector<long long> dp(n);
  for (int i = 1; i < n; i++) {
    dp[i] = query(1, 0, MAX, h[i]) - h[i] * 1LL * h[i] - pref[i - 1];
    modify(1, 0, MAX, {2 * h[i], -h[i] * 1LL * h[i] + pref[i] + dp[i]});
  }
  cout << -dp[n - 1] << '\n';
  return 0;
}

Compilation message

building.cpp: In lambda function:
building.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp: In lambda function:
building.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62932 KB Output is correct
2 Correct 25 ms 62884 KB Output is correct
3 Correct 32 ms 62912 KB Output is correct
4 Correct 31 ms 62964 KB Output is correct
5 Correct 31 ms 62920 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 65224 KB Output is correct
2 Correct 85 ms 65236 KB Output is correct
3 Correct 76 ms 65292 KB Output is correct
4 Correct 77 ms 65292 KB Output is correct
5 Correct 63 ms 65380 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62932 KB Output is correct
2 Correct 25 ms 62884 KB Output is correct
3 Correct 32 ms 62912 KB Output is correct
4 Correct 31 ms 62964 KB Output is correct
5 Correct 31 ms 62920 KB Output is correct
6 Correct 85 ms 65224 KB Output is correct
7 Correct 85 ms 65236 KB Output is correct
8 Correct 76 ms 65292 KB Output is correct
9 Correct 77 ms 65292 KB Output is correct
10 Correct 63 ms 65380 KB Output is correct
11 Correct 73 ms 66380 KB Output is correct
12 Correct 78 ms 66368 KB Output is correct
13 Correct 63 ms 66424 KB Output is correct
14 Correct 73 ms 66476 KB Output is correct
15 Correct 74 ms 66228 KB Output is correct
16 Correct 64 ms 66124 KB Output is correct
17 Correct 43 ms 66312 KB Output is correct
18 Correct 45 ms 66360 KB Output is correct