Submission #13626

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13626	2015-02-25T16:11:20 Z	gs12117	Mountain Trek Route (IZhO12_route)	C++	100 / 100	227 ms	21536 KB

route

#include<stdio.h>
#include<queue>
int n;
int a[1001000];
int b[1001000];
int m;
int ans;
int liv[1001000];
int nxt[1001000];
int prv[1001000];
struct node{
	int stp;
	int len;
	bool operator<(const node&r)const{
		return len>r.len;
	}
};
std::priority_queue<node> pq;
int main(){
	int i,j;
	node p;
	scanf("%d%d",&n,&m);
	j=0;
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		if(a[i]>a[j])j=i;
	}
	for(i=0;i<n;i++){
		b[i]=a[(i+j)%n];
	}
	b[n]=b[0];
	n++;
	j=-1;
	for(i=0;i<n;i++){
		if(i==0||b[i]!=b[i-1]){
			liv[i]=1;
			prv[i]=j;
			j=i;
		}
	}
	j=n;
	for(i=n-1;i>=0;i--){
		if(liv[i]==1){
			nxt[i]=j;
			j=i;
			if(nxt[i]!=n&&prv[i]!=-1&&b[nxt[i]]>b[i]&&b[prv[i]]>b[i]){
				p.len=nxt[i]-i;
				p.stp=i;
				pq.push(p);
			}
		}
	}
	while(m>0&&pq.size()!=0){
		p=pq.top();
		pq.pop();
		i=p.stp;
		j=m/p.len;
		if(j<b[nxt[i]]-b[i]&&j<b[prv[i]]-b[i]){
			ans+=j;
			break;
		}
		else{
			if(b[nxt[i]]-b[i]>b[prv[i]]-b[i]){
				j=b[prv[i]]-b[i];
			}
			else{
				j=b[nxt[i]]-b[i];
			}
			ans+=j;
			b[i]+=j;
			m-=j*p.len;
			if(b[i]==b[prv[i]]){
				i=prv[i];
				nxt[i]=nxt[nxt[i]];
				prv[nxt[i]]=i;
			}
			if(b[i]==b[nxt[i]]){
				nxt[i]=nxt[nxt[i]];
				prv[nxt[i]]=i;
			}
			if(nxt[i]!=n&&prv[i]!=-1&&b[nxt[i]]>b[i]&&b[prv[i]]>b[i]){
				p.len=nxt[i]-i;
				p.stp=i;
				pq.push(p);
			}
		}
	}
	printf("%d",ans*2);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	20764 KB	Output is correct
2	Correct	0 ms	20764 KB	Output is correct
3	Correct	0 ms	20764 KB	Output is correct
4	Correct	0 ms	20764 KB	Output is correct
5	Correct	0 ms	20764 KB	Output is correct
6	Correct	0 ms	20764 KB	Output is correct
7	Correct	0 ms	20764 KB	Output is correct
8	Correct	0 ms	20764 KB	Output is correct
9	Correct	0 ms	20764 KB	Output is correct
10	Correct	10 ms	20764 KB	Output is correct
11	Correct	23 ms	21536 KB	Output is correct
12	Correct	24 ms	20764 KB	Output is correct
13	Correct	191 ms	20764 KB	Output is correct
14	Correct	181 ms	20764 KB	Output is correct
15	Correct	154 ms	20764 KB	Output is correct
16	Correct	143 ms	20764 KB	Output is correct
17	Correct	174 ms	20764 KB	Output is correct
18	Correct	174 ms	20764 KB	Output is correct
19	Correct	227 ms	20764 KB	Output is correct
20	Correct	157 ms	20764 KB	Output is correct