Submission #341121

#	Time	Username	Problem	Language	Result	Execution time	Memory
341121		juggernaut	Mountain Trek Route (IZhO12_route)	C++14	100 / 100	542 ms	26152 KiB

route

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<pair<int,int>>S;
int main(){
	int n,k,ans=0;
	cin>>n>>k;
	vector<int>a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	rotate(a.begin(),max_element(a.begin(),a.end()),a.end());
	a.push_back(a[0]);
	vector<int>s;
	for(int i=0;i<=n;i++){
  		while(s.size()&&a[s.back()]<a[i]){
  			int val=a[s.back()];
  			s.pop_back();
  			S.push({s.back()+1-i,min(a[s.back()],a[i])-val});
  		}
		s.push_back(i);
	}
	while(!S.empty()){
		auto c=S.top();
		S.pop();
		c.first*=-1;
		int t=min(k/c.first,c.second);
		ans+=t<<1;
		k-=t*c.first;
	}
	cout<<ans;
}

• Subtask 1: 100 / 100