Submission #1029142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029142		avighna	Discharging (NOI20_discharging)	C++17	47 / 100	1062 ms	362576 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_min, table_max;

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

  ll query_min(ll a, ll b) {
    if (a == b) {
      return orig[a];
    }
    ll powToUse = std::ceil(std::log2(b - a + 1)) - 1;
    return std::min(table_min[powToUse][a],
                    table_min[powToUse][b - (1 << powToUse) + 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]);
  }
};

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);
  std::vector<Line> lines;
  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) {
      // val * (j - i + n - j) + dp[j]
      for (auto &l : lines) {
        dp[i] = std::min(dp[i], l(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
        lines.push_back({-val[j], dp[j] + val[j] * n});
      }
      j = i;
      active_cnt++;
    }
  }
  std::cout << dp[0] << '\n';
}

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