답안 #339871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339871 2020-12-26T10:19:50 Z Vladikus004 등산 경로 (IZhO12_route) C++14
100 / 100
197 ms 27996 KB
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 2e9
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

//#define int long long
const int N = 1000000 + 3;
int n, k, a[N], b[N], buff[N];
ll cnt[N];

ll solve(ll k){
    vector <int> st;
    for (int i = n - 1; i >= 0; i--)
        if (b[i] > 0) st.pb(i);
    for (int i = n - 1; i >= 0; i--){
        while (!st.empty() && b[st.back()] == 0) st.pop_back();
        if (b[i] > 0) st.push_back(i);
        if (b[i] < 0){
            while (b[i] < 0 && !st.empty()){
                int gt = min(-b[i], b[st.back()]);
                cnt[(st.back() + n - i) % n] += gt;
                b[st.back()] -= gt;
                b[i] += gt;
                while (!st.empty() && b[st.back()] == 0) st.pop_back();
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        ll gt = min(k/i, cnt[i]);
        k -= i * 1LL * gt;
        cnt[i] -= gt;
        ans += gt;
        cnt[i] = 0;
    }
    return ans*2LL;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    pair <ll, ll> mx = {-1, -1};
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n - 1; i++) b[i] = a[i + 1] - a[i];
    b[n - 1] = a[0] - a[n - 1];
    ll pref = 0;
    for (int i = 0; i < n; i++){
        pref += b[i];
        mx = max(mx, {pref, i});
    }
    int cnt = 0;
    for (int i = mx.second; i < n; i++)
        buff[cnt++] = b[i];
    for (int i = 0; i < mx.second; i++)
        buff[cnt++] = b[i];
    for (int i = 0; i < n; i++)
        b[i] = buff[i];
    b[n] = b[0];
    for (int j = 0; j < n; j++)
        b[j] = b[j + 1];
    ll ans = 0;
        ans = max(ans, solve(k));
    cout << ans;
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 17 ms 3176 KB Output is correct
11 Correct 17 ms 2672 KB Output is correct
12 Correct 20 ms 2796 KB Output is correct
13 Correct 163 ms 27924 KB Output is correct
14 Correct 160 ms 27984 KB Output is correct
15 Correct 161 ms 27884 KB Output is correct
16 Correct 153 ms 27996 KB Output is correct
17 Correct 149 ms 27864 KB Output is correct
18 Correct 186 ms 27856 KB Output is correct
19 Correct 197 ms 27856 KB Output is correct
20 Correct 123 ms 23904 KB Output is correct