oj.uz

Submission #434323

# Submission time Handle Problem Language Result Execution time Memory
434323 2021-06-20T23:48:38 Z JovanK26 Lightning Conductor (POI11_pio) C++14
100 / 100
 264 ms 12824 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 820 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1112 KB Output is correct
2 Correct 28 ms 1156 KB Output is correct
3 Correct 30 ms 1596 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1484 KB Output is correct
2 Correct 47 ms 2352 KB Output is correct
3 Correct 48 ms 2620 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 4232 KB Output is correct
2 Correct 119 ms 5004 KB Output is correct
3 Correct 119 ms 4952 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 8788 KB Output is correct
2 Correct 185 ms 7880 KB Output is correct
3 Correct 177 ms 8544 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 12824 KB Output is correct
2 Correct 257 ms 11020 KB Output is correct
3 Correct 250 ms 12024 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 10412 KB Output is correct
2 Correct 252 ms 11096 KB Output is correct
3 Correct 261 ms 12100 KB Output is correct