oj.uz

Submission #202994

# Submission time Handle Problem Language Result Execution time Memory
202994 2020-02-18T22:30:15 Z MKopchev Lightning Conductor (POI11_pio) C++14
91 / 100
 650 ms 14320 KB 
#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=0;
    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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1016 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1400 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1456 KB Output is correct
2 Incorrect 35 ms 1400 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2016 KB Output is correct
2 Correct 67 ms 1912 KB Output is correct
3 Correct 70 ms 2424 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 4088 KB Output is correct
2 Correct 209 ms 3960 KB Output is correct
3 Correct 229 ms 4600 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 8056 KB Output is correct
2 Correct 360 ms 5880 KB Output is correct
3 Correct 378 ms 8056 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 11128 KB Output is correct
2 Correct 611 ms 13176 KB Output is correct
3 Correct 611 ms 14200 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 8728 KB Output is correct
2 Correct 616 ms 13228 KB Output is correct
3 Correct 624 ms 14320 KB Output is correct