結果

問題 No.3646 Decrement.
コンテスト
ユーザー tnakao0123
提出日時 2026-08-26 14:36:18
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 47 ms / 2,000 ms
+ 44µs
コード長 2,387 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 341 ms
コンパイル使用メモリ 73,920 KB
実行使用メモリ 16,256 KB
最終ジャッジ日時 2026-08-26 14:36:32
合計ジャッジ時間 3,875 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 1
小課題1 5 % AC * 5
小課題2 5 % AC * 3
小課題3 20 % AC * 10
小課題4 30 % AC * 19
小課題5 10 % AC * 34
小課題6 30 % AC * 45
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3646.cc:  No.3646 Decrement. - yukicoder
 */

#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 200000;

/* typedef */

using ll = long long;

struct Node {
  int a, l, u;
  bool f;
  Node *prv, *nxt;
  Node(int _a = 0, int _l = 0, int _u = 0, bool _f = false,
       Node *_prv = nullptr, Node *_nxt = nullptr):
    a(_a), l(_l), u(_u), f(_f), prv(_prv), nxt(_nxt) {}

  Node *lmerge() {
    if (prv != nullptr && a == prv->a) {
      prv->f = true;
      u = prv->u, l += prv->l;
      prv = prv->prv;
      if (prv != nullptr) prv->nxt = this;
    }
    return this;
  }
  Node *rmerge() {
    if (nxt != nullptr && a == nxt->a) {
      nxt->f = true;
      l += nxt->l;
      nxt = nxt->nxt;
      if (nxt != nullptr) nxt->prv = this;
    }
    return this;
  }
};

struct CompNode {
  bool operator()(const Node *a, const Node *b) const {
    return a->l > b->l;
  }
};

/* global variables */

int as[MAX_N + 2];
Node *es[MAX_N + 2];

/* subroutines */

/* main */

int main() {
  int n;
  ll k;
  scanf("%d%lld", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", as + i);
  as[0] = as[n + 1] = 0;

  priority_queue<Node*,vector<Node*>,CompNode> q;
  for (int i = 1; i <= n;) {
    int j = i;
    while (i <= n && as[j] == as[i]) i++;
    auto e = new Node(as[j], i - j, j);
    es[j] = es[i - 1] = e;
    if (as[j - 1] < as[j] && as[i - 1] > as[i]) q.push(e);
  }
  es[0] = new Node(0, 1, 0);
  es[n + 1] = new Node(0, 1, n + 1);
  
  for (int i = 0; i <= n; i++)
    if (es[i] != es[i + 1] && es[i] != nullptr && es[i + 1] != nullptr) {
      es[i]->nxt = es[i + 1], es[i + 1]->prv = es[i];
    }

  while (k > 0 && ! q.empty()) {
    auto e = q.top(); q.pop();
    if (e->l > k) break;
    if (e->f) continue;

    int maxa = max(e->prv != nullptr ? e->prv->a : 0,
		   e->nxt != nullptr ? e->nxt->a : 0);
    int da = min(k / e->l, (ll)e->a - maxa);
    e->a -= da;
    k -= (ll)da * e->l;

    e->lmerge();
    e->rmerge();
    if (e->a > 0 && e->prv->a < e->a && e->a > e->nxt->a) q.push(e);
  }

  Node *rt = nullptr;
  for (int i = 0; i <= n + 1; i++)
    if (es[i] != nullptr && ! es[i]->f) { rt = es[i]; break; }

  ll sum = 0;
  while (rt != nullptr && rt->nxt != nullptr) {
    sum += abs(rt->nxt->a - rt->a);
    rt = rt->nxt;
  }

  printf("%lld\n", sum);
  
  return 0;
}
0