oj.uz

Submission #1029142

# Submission time Handle Problem Language Result Execution time Memory
1029142 2024-07-20T12:55:48 Z avighna Discharging (NOI20_discharging) C++17
47 / 100
 1000 ms 362576 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 452 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 728 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 728 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Execution timed out 1062 ms 357708 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 362436 KB Output is correct
2 Correct 266 ms 362556 KB Output is correct
3 Correct 251 ms 362560 KB Output is correct
4 Correct 231 ms 362436 KB Output is correct
5 Correct 248 ms 362572 KB Output is correct
6 Correct 271 ms 362568 KB Output is correct
7 Correct 232 ms 362428 KB Output is correct
8 Correct 260 ms 362576 KB Output is correct
9 Correct 248 ms 362300 KB Output is correct
10 Correct 213 ms 362424 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 452 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 608 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 1 ms 728 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 636 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 600 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 1 ms 604 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 604 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 0 ms 604 KB Output is correct
45 Correct 0 ms 604 KB Output is correct
46 Correct 0 ms 604 KB Output is correct
47 Correct 1 ms 600 KB Output is correct
48 Correct 1 ms 604 KB Output is correct
49 Correct 1 ms 600 KB Output is correct
50 Correct 1 ms 604 KB Output is correct

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 452 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 608 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 1 ms 728 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Execution timed out 1062 ms 357708 KB Time limit exceeded
31 Halted 0 ms 0 KB -