Submission #5173171


Source Code Expand

Copy
#include <iostream>
#include <vector>
using namespace std;

#define INF 1050000000

int main(void) {
    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    for (int i = 0; i < N; i++) {
        cin >> h[i];
    }

    // c[i] = 足場 i にたどり着くまでのコストの最小値
    vector<int> c(N, INF); // DP 配列の全要素をでっかい数で初期化
    c[0] = 0;              // c[0] が 0 であることは分かっている

    // i = 1 からループ
    for (int i = 1; i < N; i++) {
        // i-k が負にならないようにループ範囲の最大を min(i, K) に設定
        for (int k = 1; k <= min(i, K); k++) {
            c[i] = min(c[i], c[i - k] + abs(h[i - k] - h[i]));
        }
    }

    cout << c[N - 1] << endl;

    return 0;
}

Submission Info

Submission Time
Task B - Frog 2
User furuya1223
Language C++14 (GCC 5.4.1)
Score 100
Code Size 809 Byte
Status
Exec Time 45 ms
Memory 1024 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 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 1 ms 256 KB
0_01 1 ms 256 KB
0_02 1 ms 256 KB
0_03 1 ms 256 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 24 ms 1024 KB
1_03 45 ms 1024 KB
1_04 25 ms 1024 KB
1_05 25 ms 1024 KB
1_06 26 ms 1024 KB
1_07 26 ms 1024 KB
1_08 28 ms 1024 KB
1_09 30 ms 1024 KB
1_10 35 ms 1024 KB
1_11 40 ms 1024 KB