Submission #848673

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
848673	2023-09-13T08:38:20 Z	Darren0724	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	661 ms	65536 KB

route

#include <bits/stdc++.h>
using namespace std;
int32_t main() {
    int n,k;cin>>n>>k;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int p=max_element(v.begin(),v.end())-v.begin();
    rotate(v.begin(),v.begin()+p,v.end());
    v.push_back(v[0]);
    set<int> s;
    for(int i=0;i<=n;i++){
        s.insert(i);
    }
    vector<int> a;
    vector<pair<int,int>> b;
    for(int i=1;i<n;i++){
        a.push_back(i);
    }
    sort(a.begin(),a.end(),[&](int a,int b){return v[a]<v[b];});
    for(int j=0;j<n-1;j++){
        int i=a[j];
        auto it=--s.lower_bound(i);
        auto it1=s.upper_bound(i);
        b.push_back({*it1-*it-1,min(v[*it],v[*it1])-v[i]});
        s.erase(i);
    }
    sort(b.begin(),b.end());
    int ans=0;
    for(auto[p,cnt]:b){
        if(p*cnt>k){
            ans+=k/p;
            break;
        }
        ans+=cnt;
        k-=p*cnt;
    }
    cout<<ans*2<<endl;

    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	53 ms	6348 KB	Output is correct
11	Correct	101 ms	7372 KB	Output is correct
12	Correct	55 ms	6344 KB	Output is correct
13	Correct	661 ms	65536 KB	Output is correct
14	Correct	635 ms	65536 KB	Output is correct
15	Correct	623 ms	65536 KB	Output is correct
16	Correct	625 ms	65536 KB	Output is correct
17	Runtime error	587 ms	65536 KB	Execution killed with signal 9
18	Halted	0 ms	0 KB	-