oj.uz

Submission #202995

# Submission time Handle Problem Language Result Execution time Memory
202995 2020-02-18T22:32:01 Z MKopchev Lightning Conductor (POI11_pio) C++14
100 / 100
 657 ms 11256 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=-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

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 20 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1400 KB Output is correct
2 Correct 40 ms 1316 KB Output is correct
3 Correct 54 ms 1704 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1912 KB Output is correct
2 Correct 65 ms 1912 KB Output is correct
3 Correct 71 ms 2424 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 4156 KB Output is correct
2 Correct 212 ms 3960 KB Output is correct
3 Correct 213 ms 4600 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 8056 KB Output is correct
2 Correct 376 ms 5880 KB Output is correct
3 Correct 367 ms 7928 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 11256 KB Output is correct
2 Correct 620 ms 8376 KB Output is correct
3 Correct 638 ms 11256 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 8828 KB Output is correct
2 Correct 596 ms 8184 KB Output is correct
3 Correct 626 ms 11256 KB Output is correct