Submission #202995

#	Time	Username	Problem	Language	Result	Execution time	Memory
202995		MKopchev	Lightning Conductor (POI11_pio)	C++14	100 / 100	657 ms	11256 KiB

pio

#include<bits/stdc++.h>
using namespace std;
const int nmax=5e5+42;
int n,inp[nmax];

int mx_left[nmax],mx_right[nmax];

int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    int mx=-1;
    for(int i=1;i<=n;i++)
    {
        mx_left[i]=max(mx_left[i],inp[i]);
        if(mx>=inp[i])continue;
        mx=max(mx,inp[i]);

        for(int d=0;i+d*d+1<=n;d++)
        {
            int j=i+d*d+1;
            mx_left[j]=max(mx_left[j],inp[i]+d+1);
        }
    }


    for(int i=1;i<=n;i++)
    {
        mx_right[i]=max(mx_right[i],inp[i]);

        for(int d=0;i-d*d-1>=1;d++)
        {
            int j=i-d*d-1;
            mx_right[j]=max(mx_right[j],inp[i]+d+1);
        }
    }

    for(int i=1;i<=n;i++)
        mx_left[i]=max(mx_left[i],mx_left[i-1]);
    for(int i=n;i>=1;i--)
        mx_right[i]=max(mx_right[i],mx_right[i+1]);

    for(int i=1;i<=n;i++)
        printf("%i\n",max(mx_left[i],mx_right[i])-inp[i]);

    return 0;
}

Compilation message (stderr)

pio.cpp: In function 'int main()':
pio.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
pio.cpp:11:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
                          ~~~~~^~~~~~~~~~~~~~

• 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