Submission #1029248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029248		avighna	Discharging (NOI20_discharging)	C++17	20 / 100	194 ms	205260 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:
  bool parallel(const Line &a, const Line &b) { return a.m == b.m; }
  long double x_intersection(const Line &a, const Line &b) {
    return (a.b - b.b) / ((long double)(b.m - a.m));
  }

public:
  std::deque<Line> dq;

  void insert(Line l) {
    if (dq.size() >= 1 and parallel(l, dq.back()) and l.b <= dq.back().b) {
      return;
    }
    while (dq.size() >= 2) {
      if (parallel(l, dq.back())) {
        if (l.b > dq.back().b) {
          dq.pop_back();
          continue;
        } else {
          return;
        }
      }
      if (x_intersection(l, dq.back()) <=
          x_intersection(dq.back(), dq[dq.size() - 2])) {
        dq.pop_back();
      } else {
        break;
      }
    }
    if (dq.size() == 1 and parallel(l, dq.back()) and l.b > dq.back().b) {
      dq.pop_back();
    }
    dq.push_back(l);
  }

  ll query(ll x) {
    while (dq.size() >= 2 and dq[0](x) <= dq[1](x)) {
      dq.pop_front();
    }
    return dq[0](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 active_cnt = 0;
  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 (active_cnt != 0) {
      if (active_cnt > 1) {
        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;
      active_cnt++;
    }
  }
  std::cout << dp[0] << '\n';
}

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