Submission #91813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
91813	2018-12-30T07:33:53 Z	SamAnd	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	157 ms	41772 KB

route

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
#include <deque>
using namespace std;
const int N=1000006;
struct ban
{
    int l,r,x;
};

int n;
long long k;
int a[N],ll[N],rr[N];
long long b[N];
deque<ban> q;
int mm(int i)
{
    if(i==1)
        return n;
    return i-1;
}
int pp(int i)
{
    if(i==n)
        return 1;
    return i+1;
}
int main()
{
    //freopen("g.in","r",stdin);
    //freopen("g.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    ///////////////////////////////
    for(int i=1;i<=n;++i)
    {
        ban t;
        t.x=a[i];
        t.l=i;
        for(;a[i]==t.x && i<=n;++i)
            t.r=i;
        --i;
        ll[t.r]=t.l;
        rr[t.l]=t.r;
        q.push_back(t);
    }
    if(a[1]==a[n])
    {
        ban t1=q.front(),t2=q.back();
        q.pop_back();
        q.pop_front();
        ban t;
        t.x=a[1];
        t.l=t2.l;
        t.r=t1.r;
        ll[t.r]=t.l;
        rr[t.l]=t.r;
        q.push_back(t);
    }
    while(!q.empty())
    {
        ban t=q.front();
        q.pop_front();
        int l=t.l;
        int r=t.r;
        int x=t.x;
        ban h;
        if(l<=r)
        {
            if(!(a[l]<a[mm(l)] && a[r]<a[pp(r)]))
                continue;
            h.x=min(a[mm(l)],a[pp(r)]);
            b[r-l+1]+=(h.x-x);
        }
        else
        {
            if(!(a[l]<a[mm(l)] && a[r]<a[pp(r)]))
                continue;
            h.x=min(a[mm(l)],a[pp(r)]);
            b[r+n-l+1]+=(h.x-x);
        }
        h.l=l;
        h.r=r;
        if(h.x==a[mm(l)])
        {
            h.l=ll[mm(l)];
        }
        if(h.x==a[pp(r)])
        {
            h.r=rr[pp(r)];
        }
        ll[h.r]=h.l;
        rr[h.l]=h.r;
        q.push_front(h);
    }
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        long long x=(i*b[i]);
        if(k>=x)
        {
            k-=x;
            ans+=b[i];
        }
        else
        {
            ans+=(k/i);
            k=0;
            break;
        }
    }
    cout<<ans*2<<endl;
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	16 ms	4472 KB	Output is correct
11	Correct	19 ms	3832 KB	Output is correct
12	Correct	15 ms	3064 KB	Output is correct
13	Correct	157 ms	41608 KB	Output is correct
14	Correct	152 ms	41772 KB	Output is correct
15	Correct	147 ms	39688 KB	Output is correct
16	Correct	153 ms	40760 KB	Output is correct
17	Correct	146 ms	40712 KB	Output is correct
18	Correct	152 ms	41476 KB	Output is correct
19	Correct	157 ms	41608 KB	Output is correct
20	Correct	134 ms	24172 KB	Output is correct