Submission #482846

#	Time	Username	Problem	Language	Result	Execution time	Memory
482846		valerikk	Safety (NOI18_safety)	C++17	100 / 100	50 ms	3744 KiB

safety

// https://oj.uz/problem/view/NOI18_safety
#include <stdio.h>
#include <queue>
#include <vector>

int main() {
  int n;
  long long h;
  scanf("%d%lld", &n, &h);
  std::priority_queue<long long> neg;
  long long negd = 0;
  std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pos;
  long long posd = 0;
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    long long a;
    scanf("%lld", &a);
    if (i == 0) {
      neg.push(a);
      pos.push(a);
    } else {
      negd -= h;
      posd += h;
      long long l = neg.top() + negd;
      long long r = pos.top() + posd;
      if (a >= l && a <= r) {
        neg.push(a - negd);
        pos.push(a - posd);
      } else if (a > r) {
        ans += a - r;
        neg.push(r - negd);
        pos.pop();
        pos.push(a - posd);
        pos.push(a - posd);
      } else {
        ans += l - a;
        pos.push(l - posd);
        neg.pop();
        neg.push(a - negd);
        neg.push(a - negd);
      }
    }
  }
  printf("%lld\n", ans);
}

Compilation message (stderr)

safety.cpp: In function 'int main()':
safety.cpp:9:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |   scanf("%d%lld", &n, &h);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
safety.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%lld", &a);
      |     ~~~~~^~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29