oj.uz

Submission #230609

# Submission time Handle Problem Language Result Execution time Memory
230609 2020-05-10T14:53:39 Z AlexLuchianov Building Bridges (CEOI17_building) C++14
100 / 100
 127 ms 129144 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int const range = 2000000;
ll const inf = 10000000000000000LL;
ll h[1 + nmax], w[1 + nmax];

class LiChao{
private:
  struct Line{
    int a;
    ll b;
    ll eval(int x){
      return 1LL * x * a + b;
    }
  };
  vector<Line> aint;
public:
  LiChao(int n){
    aint.resize(1 + 4 * n);
  }
  void build(int node, int from, int to){
    aint[node] = {0, inf};
    if(from < to){
      int mid = (from + to) / 2;
      build(node * 2, from, mid);
      build(node * 2 + 1, mid + 1, to);
    }
  }
  void update(int node, int from, int to, Line lin){
    int mid = (from + to) / 2;

    if(lin.eval(mid) < aint[node].eval(mid))
      swap(aint[node], lin);
    if(from < to){
      if(lin.eval(from) < aint[node].eval(from))
        update(node * 2, from, mid, lin);
      else
        update(node * 2 + 1, mid + 1, to, lin);
    }
  }
  ll query(int node, int from, int to, int x){
    if(from < to){
      int mid = (from + to) / 2;
      if(x <= mid)
        return min(aint[node].eval(x), query(node * 2, from, mid, x));
      else
        return min(aint[node].eval(x), query(node * 2 + 1, mid + 1, to, x));
    } else
      return aint[node].eval(x);
  }
};
ll dp[1 + nmax];
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

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

  int n;
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> h[i];
  ll base = 0;
  for(int i = 1; i <= n; i++) {
    cin >> w[i];
    base += w[i];
    w[i] = -w[i];
  }

  LiChao cost(range);
  cost.build(1, 0, range);
  dp[1] = w[1];
  cost.update(1, 0, range, {-h[1] * 2, dp[1] + h[1] * h[1]});

  for(int i = 2;i <= n; i++){
    dp[i] = cost.query(1, 0, range, h[i]) + h[i] * h[i] + w[i];
    cost.update(1, 0, range, {-h[i] * 2, dp[i] + h[i] * h[i]});
  }

  cout << base + dp[n];
  return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:89:35: warning: narrowing conversion of '((- h[1]) * 2)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
   cost.update(1, 0, range, {-h[1] * 2, dp[1] + h[1] * h[1]});
                             ~~~~~~^~~
building.cpp:93:37: warning: narrowing conversion of '((- h[i]) * 2)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
     cost.update(1, 0, range, {-h[i] * 2, dp[i] + h[i] * h[i]});
                               ~~~~~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125688 KB Output is correct
2 Correct 73 ms 125688 KB Output is correct
3 Correct 74 ms 125560 KB Output is correct
4 Correct 72 ms 125688 KB Output is correct
5 Correct 74 ms 125688 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 129016 KB Output is correct
2 Correct 117 ms 129088 KB Output is correct
3 Correct 118 ms 129016 KB Output is correct
4 Correct 114 ms 128888 KB Output is correct
5 Correct 111 ms 128888 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 125688 KB Output is correct
2 Correct 73 ms 125688 KB Output is correct
3 Correct 74 ms 125560 KB Output is correct
4 Correct 72 ms 125688 KB Output is correct
5 Correct 74 ms 125688 KB Output is correct
6 Correct 118 ms 129016 KB Output is correct
7 Correct 117 ms 129088 KB Output is correct
8 Correct 118 ms 129016 KB Output is correct
9 Correct 114 ms 128888 KB Output is correct
10 Correct 111 ms 128888 KB Output is correct
11 Correct 125 ms 129144 KB Output is correct
12 Correct 124 ms 129016 KB Output is correct
13 Correct 117 ms 129016 KB Output is correct
14 Correct 127 ms 129144 KB Output is correct
15 Correct 113 ms 128888 KB Output is correct
16 Correct 123 ms 128888 KB Output is correct
17 Correct 105 ms 129016 KB Output is correct
18 Correct 109 ms 129016 KB Output is correct