結果

問題 No.3646 Decrement.
コンテスト
ユーザー Hari Aakash K
提出日時 2026-10-04 01:39:33
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 49 ms / 2,000 ms
+ 697µs
コード長 2,746 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,322 ms
コンパイル使用メモリ 358,116 KB
実行使用メモリ 9,912 KB
最終ジャッジ日時 2026-10-04 01:39:44
合計ジャッジ時間 8,034 ms
ジャッジサーバーID
（参考情報） 		judge4_1 / judge3_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 

#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

void fastio() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main() {
    int n;
    lli k;
    scd(n);
    sclld(k);

    vll vec(n+2);

    lli tot = 0;

    forr(i, 1, n+1) {
        sclld(vec[i]);
        tot += abs(vec[i] - vec[i-1]);
    }

    tot += vec[n];

    set<pair<int, int>> st;

    vi rn(n+2);

    frange(i, n+2) {
        int j = i;
        while(j+1 <= n + 1 && vec[j+1] == vec[i]) {
            j++;
        }
        rn[j] = i;
        rn[i] = j;
        if(i > 0 && vec[i] > vec[i-1] && j <= n && vec[j] > vec[j+1]) {
            st.insert(mp(j - i + 1, i));
        }
        i = j;
    }

    while(k > 0 && st.size()) {
        auto p = *st.begin();
        st.erase(st.begin());
        int l = p.s;
        int r = p.s + p.f - 1;

        lli d = min(vec[l] - vec[l-1], vec[r] - vec[r+1]);

        lli v = min(d, k/p.f);

        tot -= 2 * v;
        k -= v*p.f;

        vec[r] -= v;
        if(r > l)
            vec[l] -= v;

        

        if(max(vec[l-1], vec[r+1]) > 0) {
            if(vec[l-1] > vec[r+1]) {
                int l2 = rn[l-1];
                if(l2 > 0 && vec[l2] > vec[l2-1]) {
                    st.insert(mp(r - l2 + 1, l2));
                }
            }
            else if(vec[r+1] > vec[l-1]) {
                int r2 = rn[r+1];
                if(r2 <= n && vec[r2] > vec[r2+1]) {
                    st.insert(mp(r2 - l + 1, l));
                }
            }
            else {
                int l2 = rn[l-1];
                int r2 = rn[r+1];
                if(l2 > 0 && vec[l2] > vec[l2-1] && r2 <= n && vec[r2] > vec[r2+1]) {
                    st.insert(mp(r2 - l2 + 1, l2));
                }
            }
        }

        if(vec[l-1] > vec[r+1]) {
            rn[r] = rn[l-1];
            rn[rn[l-1]] = r;
        }
        else if(vec[r+1] > vec[l-1]) {
            rn[l] = rn[r+1];
            rn[rn[r+1]] = l;
        }
        else {
            int r2 = rn[rn[r+1]];
            int l2 = rn[rn[l-1]];
            rn[l2] = r2;
            rn[r2] = l2;
        }
    }
    printf("%lld\n", tot);
}
0