Submission #1208989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208989		thewizardman	Stove (JOI18_stove)	C++20	100 / 100	21 ms	3012 KiB

stove

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define iii tuple<pii, int, int>

int n, k, t[100000], ans;
pii st[200000];
priority_queue<iii> pq;

pii query(int l, int r) {
  pii ret = {0, 0};
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) ret = max(ret, st[l++]);
    if (r&1) ret = max(st[--r], ret);
  }
  return ret;
}

int main() {
  scanf("%d %d\n", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d\n", &t[i]); n--;
  ans = t[n] - t[0] + 1;
  for (int i = 0; i < n; i++) st[i+n] = {t[i+1] - t[i] - 1, i};
  for (int i = n-1; i > 0; i--) st[i] = max(st[i<<1], st[i<<1|1]);
  pq.push({query(0, n), 0, n});
  while (--k && !pq.empty()) {
    auto [p, l, r] = pq.top(); pq.pop();
    if (p.first <= 0) break;
    // cout << p.first << ' ' << p.second << ' ' << l << ' ' << r << '\n';
    ans -= p.first;
    if (l < p.second) pq.push({query(l, p.second), l, p.second});
    if (r > p.second + 1) pq.push({query(p.second + 1, r), p.second + 1, r});
  }
  printf("%d", ans);
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d %d\n", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
stove.cpp:21:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   for (int i = 0; i < n; i++) scanf("%d\n", &t[i]); n--;
      |                               ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50