Submission #13660711


Source Code Expand

Copy
#include <iostream>
#include <algorithm>
#include <vector>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
const int INF = 1e9 + 5;

signed main() {
    FAST_IO;

    int n, k;
    cin >> n >> k;
    vector<int> stones(n);
    for (int i = 0; i < n; i++) cin >> stones[i];

    vector<int> dp(n, INF); // dp[i] : Minimum cost to reach stone i.
    dp[0] = 0; // Base case, we start on the first stone so cost to reach it is 0.

    for (int i = 0; i < n; i++) { // i represents the stone the frog is currently at.
        for (int j = i + 1; j <= i + k; j++) { // j represents a potential stone for the frog to jump to.
            if (j < n)
                // Storing the total minimum cost to reach stone j from stone i.
                dp[j] = min(dp[j], dp[i] + abs(stones[j] - stones[i]));
        }
    }
    cout << dp[n - 1];
    return 0;
}

Submission Info

Submission Time
Task B - Frog 2
User arujbansal
Language C++14 (GCC 5.4.1)
Score 100
Code Size 919 Byte
Status AC
Exec Time 27 ms
Memory 1024 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 16
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11
Case Name Status Exec Time Memory
0_00 AC 1 ms 256 KB
0_01 AC 1 ms 256 KB
0_02 AC 1 ms 256 KB
0_03 AC 1 ms 256 KB
1_00 AC 1 ms 256 KB
1_01 AC 1 ms 256 KB
1_02 AC 8 ms 1024 KB
1_03 AC 27 ms 1024 KB
1_04 AC 9 ms 1024 KB
1_05 AC 9 ms 1024 KB
1_06 AC 10 ms 1024 KB
1_07 AC 10 ms 1024 KB
1_08 AC 11 ms 1024 KB
1_09 AC 14 ms 1024 KB
1_10 AC 20 ms 1024 KB
1_11 AC 26 ms 1024 KB