Submission #434323

#	Time	Username	Problem	Language	Result	Execution time	Memory
434323		JovanK26	Lightning Conductor (POI11_pio)	C++14	100 / 100	264 ms	12824 KiB

pio

#include <bits/stdc++.h>

using namespace std;
int n;
int h[500005];
int f[500005];
void rec(int l,int r,int optl,int optr)
{
    if(l>r)return;
    int i=(l+r)/2;
    int opt=optl;
    for(int j=optl;j<=min(i,optr);j++)
    {
        if(h[j]+sqrt(abs(i-j))>h[opt]+sqrt(abs(i-opt)))
        {
            opt=j;
        }
    }
    f[i]=max(f[i],h[opt]+(int)ceil(sqrt(abs(i-opt)))-h[i]);
    rec(l,i-1,optl,opt);
    rec(i+1,r,opt,optr);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> h[i];
    }
    rec(1,n,1,n);
    reverse(h+1,h+n+1);
    reverse(f+1,f+n+1);
    rec(1,n,1,n);
    for(int i=n;i>=1;i--)
    {
        cout << f[i]<<'\n';
    }
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10