Wonderful Jump solution codeforces – You are given an array of positive integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an of length 𝑛n.
Wonderful Jump solution codeforces
In one operation you can jump from index 𝑖i to index 𝑗j (1≤𝑖≤𝑗≤𝑛1≤i≤j≤n) by paying min(𝑎𝑖,𝑎𝑖+1,…,𝑎𝑗)⋅(𝑗−𝑖)2min(ai,ai+1,…,aj)⋅(j−i)2 eris.
For all 𝑘k from 11 to 𝑛n, find the minimum number of eris needed to get from index 11 to index 𝑘k.
The first line contains a single integer 𝑛n (2≤𝑛≤4⋅1052≤n≤4⋅105).
The second line contains 𝑛n integers 𝑎1,𝑎2,…𝑎𝑛a1,a2,…an (1≤𝑎𝑖≤𝑛1≤ai≤n).
Output 𝑛n integers — the 𝑘k-th integer is the minimum number of eris needed to reach index 𝑘k if you start from index 11.
Wonderful Jump solution codeforces
3 2 1 3
0 1 2
Wonderful Jump solution codeforces
6 1 4 1 6 3 2
0 1 2 3 6 8
2 1 2
0 1
4 1 4 4 4
0 1 4 8
Wonderful Jump solution codeforces
In the first example:
- From 11 to 11: the cost is 00,
- From 11 to 22: 1→21→2 — the cost is min(2,1)⋅(2−1)2=1min(2,1)⋅(2−1)2=1,
- From 11 to 33: 1→2→31→2→3 — the cost is min(2,1)⋅(2−1)2+min(1,3)⋅(3−2)2=1+1=2min(2,1)⋅(2−1)2+min(1,3)⋅(3−2)2=1+1=2.
In the fourth example from 11 to 44: 1→3→41→3→4 — the cost is min(1,4,4)⋅(3−1)2+min(4,4)⋅(4−3)2=4+4=8min(1,4,4)⋅(3−1)2+min(4,4)⋅(4−3)2=4+4=8.
Also read: Partial Sorting solution codeforces