Submission #339864

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339864	2020-12-26T10:09:02 Z	Vladikus004	Mountain Trek Route (IZhO12_route)	C++14	100 / 100	198 ms	57044 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], cnt[N], buff[N];

ll solve(int 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();
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++){
        int gt = min(k/i, cnt[i]);
        k -= i * gt;
        cnt[i] -= gt;
        ans += gt;
        cnt[i] = 0;
    }
    return ans*2;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    freopen("input.txt", "r", stdin);
    cin >> n >> k;
    pii 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];
    int 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	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	492 KB	Output is correct
10	Correct	17 ms	5220 KB	Output is correct
11	Correct	19 ms	5100 KB	Output is correct
12	Correct	17 ms	5352 KB	Output is correct
13	Correct	198 ms	57016 KB	Output is correct
14	Correct	178 ms	57044 KB	Output is correct
15	Correct	165 ms	55128 KB	Output is correct
16	Correct	175 ms	56012 KB	Output is correct
17	Correct	170 ms	56148 KB	Output is correct
18	Correct	175 ms	56780 KB	Output is correct
19	Correct	176 ms	57036 KB	Output is correct
20	Correct	137 ms	45528 KB	Output is correct