Submission #1029258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029258		avighna	Discharging (NOI20_discharging)	C++17	100 / 100	201 ms	202832 KiB

Discharging

#include <bits/stdc++.h>

typedef long long ll;

struct Line {
  ll m, b;

  Line() {}
  Line(ll m, ll b) : m(m), b(b) {}

  ll operator()(ll x) { return m * x + b; }
};

class SparseTable {
public:
  ll maxPow;
  std::vector<ll> orig;
  std::vector<std::vector<ll>> table_max;

  SparseTable(const std::vector<ll> &x) {
    orig = x;
    const ll n = x.size();
    maxPow = std::floor(std::log2(n));
    table_max = std::vector<std::vector<ll>>(maxPow + 1, std::vector<ll>(n));
    for (ll i = 0; i < n; ++i) {
      table_max[0][i] = x[i];
    }
    for (ll power = 1; power <= maxPow; ++power) {
      for (ll i = 0; i < n - (1 << (power - 1)); ++i) {
        table_max[power][i] =
            std::max(table_max[power - 1][i],
                     table_max[power - 1][i + (1 << (power - 1))]);
      }
    }
  }

  ll query_max(ll a, ll b) {
    if (a == b) {
      return orig[a];
    }
    ll powToUse = std::ceil(std::log2(b - a + 1)) - 1;
    return std::max(table_max[powToUse][a],
                    table_max[powToUse][b - (1 << powToUse) + 1]);
  }
};

class CHT {
private:
  long double x_intersect(const Line &l1, const Line &l2) {
    return -(l1.b - l2.b) / ((long double)(l1.m - l2.m));
  }

public:
  std::deque<Line> dq;

  void insert(Line l) {
    while (dq.size() > 1 &&
           x_intersect(dq[0], dq[1]) <= x_intersect(dq[0], l)) {
      dq.pop_front();
    }
    dq.push_front(l);
  }

  ll query(ll x) {
    while (dq.size() > 1 && dq[dq.size() - 1](x) <= dq[dq.size() - 2](x)) {
      dq.pop_back();
    }
    return dq.back()(x);
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n;
  std::cin >> n;
  std::vector<ll> a(n);
  for (auto &i : a) {
    std::cin >> i;
  }

  std::vector<bool> active(n);
  std::vector<ll> val(n);
  for (ll i = 0, mx = 0; i < n; ++i) {
    if (a[i] > mx) {
      mx = a[i];
      val[i] = mx;
      active[i] = true;
    }
  }
  for (ll i = 0, prev = -1; i < n; ++i) {
    if (active[i]) {
      std::swap(prev, val[i]);
    }
  }

  std::vector<ll> dp(n);
  ll suff_max = 0;
  ll j = -1;
  SparseTable table(a);
  CHT convex_hull;
  for (ll i = n - 1; i >= 0; --i) {
    suff_max = std::max(suff_max, a[i]);
    dp[i] = suff_max * (n - i);
    if (!convex_hull.dq.empty()) {
      dp[i] = std::min(dp[i], -convex_hull.query(i));
    }
    if (j != -1) {
      dp[i] = std::min(dp[i], table.query_max(i, j - 1) * (n - i) + dp[j]);
    }
    if (active[i]) {
      if (j != -1) {
        // = (-val) * i + dp[j] + val * n
        ll m = -val[j];
        ll b = dp[j] + val[j] * n;
        // insertion is now largest to smallest based on slope
        convex_hull.insert({-m, -b});
      }
      j = i;
    }
  }
  std::cout << dp[0] << '\n';
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28