Submission #339871

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339871	2020-12-26T10:19:50 Z	Vladikus004	Mountain Trek Route (IZhO12_route)	C++14	100 / 100	197 ms	27996 KB

route

#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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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