oj.uz

Submission #979179

# Submission time Handle Problem Language Result Execution time Memory
979179 2024-05-10T10:38:36 Z mannshah1211 Building Bridges (CEOI17_building) C++17
100 / 100
 34 ms 8528 KB 
/**
 *    author: hashman
 *    created:
**/
#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using Int = long long;

const Int inf = 3e18;

struct Line {
  Int a, b;
  
  Line() : a(0), b(-inf) {}
  
  Line(Int aa, Int bb) : a(aa), b(bb) {}
  
  Int eval(Int x) {
    return a * x + b;
  }
};

struct node {
  Line line = Line();
  node *l = nullptr;
  node *r = nullptr;
};

node *root;

void insert_line_knowingly(Line x, node* &nd, Int tl, Int tr) {
  if (nd == nullptr) {
    nd = new node();
  }
  if (nd->line.eval(tl) < x.eval(tl)) {
    swap(nd->line, x);
  }
  if (nd->line.eval(tr - 1) >= x.eval(tr - 1)) {
    return;
  }
  if (tr - tl == 1) {
    return;
  }
  Int tm = (tl + tr) / 2;
  if (nd->line.eval(tm - 1) > x.eval(tm - 1)) {
    insert_line_knowingly(x, nd->r, tm, tr);
  } else {
    swap(nd->line, x);
    insert_line_knowingly(x, nd->l, tl, tm);
  }
}

void insert_line(Line x, Int l, Int r, node* &nd, Int tl, Int tr) {
  if (tl >= r || l >= tr || tl >= tr || l >= r) {
    return;
  }
  if (nd == nullptr) {
    nd = new node();
  }
  if (tl >= l && tr <= r) {
    return insert_line_knowingly(x, nd, tl, tr);
  }
  Int tm = (tl + tr) / 2;
  insert_line(x, l, r, nd->l, tl, tm);
  insert_line(x, l, r, nd->r, tm, tr);
}

Int query(Int x, node *nd, Int tl, Int tr) {
  if (nd == nullptr) {
    return -inf;
  }
  if (tr - tl == 1) {
    return nd->line.eval(x);
  }
  Int res = nd->line.eval(x);
  Int tm = (tl + tr) / 2;
  if (x < tm) {
    res = max(res, query(x, nd->l, tl, tm));
  } else {
    res = max(res, query(x, nd->r, tm, tr));
  }
  return res;
}

const Int sz = 2e6;

void insert_line(Line x, Int l = 0, Int r = sz) {
  return insert_line(x, l, r, root, 0, sz);
}

Int query(Int x) {
  return query(x, root, 0, sz);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<Int> h(n + 1), w(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
  }
  vector<Int> dp(n + 1);
  dp[1] = -w[1];
  for (int i = 2; i <= n; i++) {
    insert_line(Line{2 * h[i - 1], -(dp[i - 1] + h[i - 1] * h[i - 1])});
    dp[i] = -query(h[i]) - w[i] + h[i] * h[i];
  }
  cout << accumulate(w.begin(), w.end(), Int(0)) + dp[n] << '\n';
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4012 KB Output is correct
2 Correct 32 ms 4084 KB Output is correct
3 Correct 32 ms 3932 KB Output is correct
4 Correct 31 ms 3776 KB Output is correct
5 Correct 26 ms 5244 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 33 ms 4012 KB Output is correct
7 Correct 32 ms 4084 KB Output is correct
8 Correct 32 ms 3932 KB Output is correct
9 Correct 31 ms 3776 KB Output is correct
10 Correct 26 ms 5244 KB Output is correct
11 Correct 34 ms 4124 KB Output is correct
12 Correct 32 ms 4068 KB Output is correct
13 Correct 31 ms 3944 KB Output is correct
14 Correct 32 ms 4080 KB Output is correct
15 Correct 29 ms 8528 KB Output is correct
16 Correct 24 ms 5204 KB Output is correct
17 Correct 13 ms 3676 KB Output is correct
18 Correct 13 ms 3676 KB Output is correct