Submission #848669

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
848669	2023-09-13T08:36:44 Z	Darren0724	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	699 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<pair<int,int>> a,b;
    for(int i=1;i<n;i++){
        a.push_back({v[i],i});
    }
    sort(a.begin(),a.end());
    for(int j=0;j<n-1;j++){
        int i=a[j].second;
        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	1 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	51 ms	6832 KB	Output is correct
11	Correct	102 ms	7820 KB	Output is correct
12	Correct	53 ms	6860 KB	Output is correct
13	Correct	669 ms	65536 KB	Output is correct
14	Correct	699 ms	65536 KB	Output is correct
15	Correct	638 ms	65536 KB	Output is correct
16	Correct	674 ms	65536 KB	Output is correct
17	Runtime error	602 ms	65536 KB	Execution killed with signal 9
18	Halted	0 ms	0 KB	-