SyntaxPilot
Courses/Competitive Programming/Lesson 41
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 41 of 90

DP optimisation 1: monotonic queue and prefix-min tricks

queued

These are the notes for Competitive Programming episode 41, the first part of the DP optimisation block. For the last nine episodes you learned how to find the right DP. Now we make the right DP fast: the states and the answer stay the same, but each transition gets cheaper. At Diwali, Meera has to light a lane of n lamp posts. Each post has a cost, the first and last posts must be lit, and two lit posts may be at most k apart. An original problem, Lantern Lane, asks for the cheapest plan. The DP is short: dp[i] = c[i] + min(dp[j]) over the window i − k ≤ j < i. Looping over the window is correct but takes O(n·k), which is TLE at n = 10^6. A single running minimum is fast but wrong (8 instead of 14), because it remembers posts that have already left the window. That running minimum is still a real technique, the prefix-min trick, when windows only grow. The fix for a sliding window is the monotonic deque, which is O(n) in total. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler), and all outputs below are real.

The real-life hook

Meera is the secretary of her housing society, and at Diwali she lights the main lane. The lane has n lamp posts in a row. Lighting a post costs money for wiring, a bulb and a ladder, and some posts are much cheaper than others. The society does not want a long dark stretch, so two lit posts that are next to each other in the plan can be at most k positions apart. The gate at the start and the temple at the end must be lit. What is the cheapest plan?

Problem R · Lantern Lane

(Written for this course, in the style of an AtCoder Beginner Contest problem.)

Posts 0 … n − 1, and lighting post i costs c[i]. Light post 0 and post n − 1. Any two consecutive lit posts must be at most k apart, so at most k − 1 dark posts sit between them. Print the minimum total cost.

  • Input: n and k, then c[0] … c[n − 1].
  • Constraints: 1 ≤ k ≤ n ≤ 10^6, 1 ≤ c[i] ≤ 10^9.
  • Output: the minimum total cost.
Input Output Why
8 3 / 3 9 4 7 8 2 6 5 14 light posts 0, 2, 5, 7: 3 + 4 + 2 + 5
5 2 / 1 100 1 100 1 3 light every cheap post: 0, 2, 4
1 1 / 7 7 one post is both the first and the last

The DP. Let dp[i] be the cheapest plan whose last lit post is i. The lit post before i is some j from the last k posts:

dp[0] = c[0], dp[i] = c[i] + min over i − k ≤ j < i of dp[j]

The answer is dp[n − 1]. The state (dp[i]) and the transition (minimum over a window) are both correct. Only the speed of the transition is a problem.

Attempt 1: loop over the window (correct, but TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> c(n);
    for (ll &x : c) cin >> x;
    vector<ll> dp(n);                         // dp[i] = cheapest plan with post i lit last
    dp[0] = c[0];
    for (int i = 1; i < n; i++) {
        ll best = LLONG_MAX;
        for (int j = max(0, i - k); j < i; j++)  // previous lit post: at most k back
            best = min(best, dp[j]);
        dp[i] = c[i] + best;
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

Sample 1 prints 14 and sample 2 prints 3, so both are correct. Next is the worst case: n = 10^6 and k = 5 · 10^5. This version builds that input itself:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000, k = 500000;          // worst case, built here
    vector<ll> c(n);
    mt19937 rng(41);
    for (ll &x : c) x = rng() % 1000000000 + 1;
    vector<ll> dp(n);
    dp[0] = c[0];
    for (int i = 1; i < n; i++) {
        ll best = LLONG_MAX;
        for (int j = max(0, i - k); j < i; j++)
            best = min(best, dp[j]);
        dp[i] = c[i] + best;
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

The result is Time Limit Exceeded. On our machine the program was still running when we stopped it after 30 seconds. The inner loop runs about n · k = 5 · 10^11 times, while a contest allows roughly 10^8 simple steps per second.

Where does the time go?

  • The window for i is j = i − k … i − 1.
  • The window for i + 1 is j = i − k + 1 … i.

The two windows share k − 1 values, yet the loop scans all of them again. The window slid by one: one value came in and one value left. The goal is to reuse the last answer and get each window's minimum in O(1).

Attempt 2: a running minimum (fast, but WA)

Keep a single variable best, the minimum of every dp computed so far:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> c(n);
    for (ll &x : c) cin >> x;
    vector<ll> dp(n);
    dp[0] = c[0];
    ll best = dp[0];                          // running minimum of all dp[j] so far
    for (int i = 1; i < n; i++) {
        dp[i] = c[i] + best;
        best = min(best, dp[i]);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

Sample 1 prints 8 when the answer is 14, so this is Wrong Answer. The 8 is 3 + 5: post 0 and then straight to post 7, a gap of 7 when k is 3. A running minimum never forgets a value, so it keeps using posts that have already left the window. (The variable k is read and then never used, which is a warning sign in itself.)

The prefix-min trick: where a running minimum IS right

If every window starts at 0, the windows only grow and nothing ever leaves. Then "minimum so far" is exactly the window minimum, and a single variable gives it in O(1). This is the prefix-min trick: the window minimum is just a prefix minimum.

A variant where it fits. Drop the k limit. Instead, the municipality charges a fine of p for every dark post. Now

dp[i] = c[i] + min over j < i of ( dp[j] + p · (i − j − 1) )

The value inside the min depends on i, so you cannot just remember one minimum. Expand it: p · (i − j − 1) = p · (i − 1) − p · j. The part with i is the same for every j, so pull it out of the min:

dp[i] = c[i] + p · (i − 1) + min over j < i of ( dp[j] − p · j )

What is left inside, dp[j] − p · j, belongs to j alone. Keep a running minimum of that value. In short: separate the i-part from the j-part.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    ll p;                                     // p = fine for each dark post
    cin >> n >> p;
    vector<ll> c(n);
    for (ll &x : c) cin >> x;
    vector<ll> dp(n);
    dp[0] = c[0];
    ll best = dp[0] - p * 0;                  // min over j of (dp[j] - p*j)
    for (int i = 1; i < n; i++) {
        dp[i] = c[i] + p * (i - 1) + best;      // i-part outside, j-part inside the min
        best = min(best, dp[i] - p * i);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

The input 6 2 / 3 9 4 7 8 5 (six posts, a fine of 2) prints 16. The best plan lights only the two ends: 3 + 5, plus four dark posts at 2 each. This is correct and takes O(1) per post. It works because the window only grows.

The monotonic deque

Picture a price board at the mandi that shows the cheapest tomato price of the last k days. Each day one price joins the board and one gets too old.

  • A vendor from Monday charges 40, and a new vendor on Wednesday charges 30. Monday's vendor will never be the cheapest again: he is more expensive, and he will expire sooner. Cross him off for good.
  • When the oldest vendor on the list is more than k days old, he drops off the front.

The list that is left runs from oldest to newest, and its prices only go up, so the cheapest price is always at the front. In code this list is a deque (double-ended queue), a queue you can pop from both ends. It holds indices, oldest at the front, and their dp values increase from front to back. A deque kept in sorted order like this is called a monotonic deque (or monotonic queue).

For each post i:

  1. while front < i − k: pop_front removes indices that left the window.
  2. dp[i] = c[i] + dp[front], because the front is the window minimum.
  3. while dp[back] ≥ dp[i]: pop_back removes entries that are older and not cheaper, which makes them useless forever.
  4. push_back(i).

Why it is O(n). There is a loop inside a loop, but every index is pushed once and popped at most once, so all the pops together number at most n. The total work is O(n), which is amortised O(1) per post.

Trace on sample 1 (n = 8, k = 3)

i c[i] window front used dp[i] popped deque after
0 3 – – 3 – 0
1 9 0..0 0 (dp 3) 12 – 0, 1
2 4 0..1 0 (dp 3) 7 back 1 (12 ≥ 7) 0, 2
3 7 0..2 0 (dp 3) 10 – 0, 2, 3
4 8 1..3 2 (dp 7) 15 front 0 (too old) 2, 3, 4
5 2 2..4 2 (dp 7) 9 back 4, 3 (15, 10 ≥ 9) 2, 5
6 6 3..5 5 (dp 9) 15 front 2 (too old) 5, 6
7 5 4..6 5 (dp 9) 14 back 6 (15 ≥ 14) 5, 7

Every row was printed by an instrumented copy of the accepted code. The dp values in the deque always increase from front to back, for example 3, 7, 10 at i = 3. Following the front used gives the plan 7 ← 5 ← 2 ← 0, which costs 5 + 2 + 4 + 3 = 14.

The accepted solution

This is the contest template, with fast input because 10^6 numbers must be read:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> c(n);
    for (ll &x : c) cin >> x;
    vector<ll> dp(n);
    dp[0] = c[0];
    deque<int> q;                     // indices; dp increases front to back
    q.push_back(0);
    for (int i = 1; i < n; i++) {
        while (q.front() < i - k) q.pop_front();  // left the window
        dp[i] = c[i] + dp[q.front()];             // front = window minimum
        while (!q.empty() && dp[q.back()] >= dp[i]) q.pop_back();  // useless
        q.push_back(i);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}
Input Output
8 3 / 3 9 4 7 8 2 6 5 14
5 2 / 1 100 1 100 1 3
1 1 / 7 7

The q.front() call in the first while is always safe. Index i − 1 is pushed last and is never older than i − k, because k ≥ 1, so the deque never empties there.

The worst case from Attempt 1 uses the same body, with the input built inside the program:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000, k = 500000;          // worst case, built here
    vector<ll> c(n);
    mt19937 rng(41);
    for (ll &x : c) x = rng() % 1000000000 + 1;
    vector<ll> dp(n);
    dp[0] = c[0];
    deque<int> q;                     // indices; dp increases front to back
    q.push_back(0);
    for (int i = 1; i < n; i++) {
        while (q.front() < i - k) q.pop_front();  // left the window
        dp[i] = c[i] + dp[q.front()];             // front = window minimum
        while (!q.empty() && dp[q.back()] >= dp[i]) q.pop_back();  // useless
        q.push_back(i);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

It prints 186608096 in 0.05 s. The window loop was still running after 30 s on the same input.

Stress test against the window loop

The fast answer on large inputs cannot be checked by hand. Instead, compare it with the slow loop, which is obviously correct, on 1000 random small lanes:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll brute(int n, int k, vector<ll>& c) {
    vector<ll> dp(n);
    dp[0] = c[0];
    for (int i = 1; i < n; i++) {
        ll best = LLONG_MAX;
        for (int j = max(0, i - k); j < i; j++) best = min(best, dp[j]);
        dp[i] = c[i] + best;
    }
    return dp[n - 1];
}
ll fast(int n, int k, vector<ll>& c) {
    vector<ll> dp(n);
    dp[0] = c[0];
    deque<int> q{0};
    for (int i = 1; i < n; i++) {
        while (q.front() < i - k) q.pop_front();
        dp[i] = c[i] + dp[q.front()];
        while (!q.empty() && dp[q.back()] >= dp[i]) q.pop_back();
        q.push_back(i);
    }
    return dp[n - 1];
}
int main() {
    mt19937 rng(7);
    for (int t = 1; t <= 1000; t++) {
        int n = rng() % 10 + 1, k = rng() % n + 1;
        vector<ll> c(n);
        for (ll &x : c) x = rng() % 20 + 1;
        if (brute(n, k, c) != fast(n, k, c)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 1000 tests passed";
}

Output: all 1000 tests passed. Small n (1 … 10) and small costs (1 … 20) create many ties and edge cases such as n = 1 and k = n. If there is a bug, a small test case usually finds it.

The int overflow bug

Every post costs 10^9 and k = 2, so about half of the 10^6 posts must be lit. Someone wrote vector<int> for dp:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000, k = 2;               // every post costs 10^9
    vector<ll> c(n, 1000000000);
    vector<int> dp(n);                        // int is enough?
    dp[0] = c[0];
    deque<int> q;                     // indices; dp increases front to back
    q.push_back(0);
    for (int i = 1; i < n; i++) {
        while (q.front() < i - k) q.pop_front();  // left the window
        dp[i] = c[i] + dp[q.front()];             // front = window minimum
        while (!q.empty() && dp[q.back()] >= dp[i]) q.pop_back();  // useless
        q.push_back(i);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

The program prints -1121117184, a negative cost, with no error and no warning. The sums passed the int limit of about 2.1 · 10^9 and wrapped around. Change the line back to vector<ll> dp(n); and the same program prints 500001000000000: 500001 lit posts × 10^9. The rule: a sum of up to 10^6 values of size 10^9 needs long long.

Complexity vs the constraints

Approach Time Memory Verdict
loop over the window O(n · k) = 5 · 10^11 O(n) TLE (still running after 30 s)
running minimum of all dp O(n) O(n) Wrong Answer (8, expected 14)
multiset holding the window's dp values O(n log n) ≈ 2 · 10^7 O(n) passes (1.3–2.4 s on the worst case here)
monotonic deque O(n) = 10^6 O(n) accepted (0.05–0.14 s)

The multiset alternative is useful when you do not trust yourself with the deque. Insert dp[i], erase the dp value that left the window, and read the smallest:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> c(n);
    for (ll &x : c) cin >> x;
    vector<ll> dp(n);
    dp[0] = c[0];
    multiset<ll> win{dp[0]};                     // dp values of the window
    for (int i = 1; i < n; i++) {
        if (i - k - 1 >= 0) win.erase(win.find(dp[i - k - 1]));  // left the window
        dp[i] = c[i] + *win.begin();             // smallest in the window
        win.insert(dp[i]);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

It prints 14, 3 and 7 on the three samples. On a random file with n = 10^6 and k = 5 · 10^5, it gives the same answer as the deque (1270587369), but it takes 1.3–2.4 s against about 0.12 s for the deque. Use win.erase(win.find(v)) and not win.erase(v), because the second form erases every copy of v.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
loop over the whole window Time Limit Exceeded O(n · k) monotonic deque
running min on a sliding window 8 (expected 14) uses expired j pop_front old indices
read the front without first popping expired indices 8 (expected 14) the front may be expired pop_front, then read
q.front() <= i - k instead of < 21 and 203 (expected 14 and 3) the window shrinks to k − 1 the window is i − k … i − 1, so pop while < i - k
vector<int> dp -1121117184 sum > 2.1 · 10^9 vector<long long>
multiset::erase(value) removes all equal values erase by value erases every copy erase(find(value))
pushing values instead of indices cannot tell which entry expired expiry depends on position store indices, look up dp[index]

Mini project

Build a "Diwali lighting planner". Read the lane (n, k and the costs) and print the cheapest cost and the list of posts to light (practice 1). Then add a mode switch:

  • gap mode: lit posts at least a and at most k apart (practice 2);
  • fine mode: no k limit, but a fine p per dark post (the prefix-min trick);
  • beauty mode: maximise total beauty, where values may be negative (practice 3).

Check every mode against an O(n · k) brute force with a stress test of 1000 random lanes before trusting it, and time each mode on n = 10^6.

Practice

These are the homework questions from the video. Every answer below was compiled and run, and each solution was also checked against a brute force on 400 random cases.

1. Print which posts to light, not just the cost.

Solution

Store from[i] = q.front(), the index that gave dp[i] its minimum, and walk back from n − 1.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> c(n);
    for (ll &x : c) cin >> x;
    vector<ll> dp(n);
    vector<int> from(n, -1);                  // from[i] = previous lit post
    dp[0] = c[0];
    deque<int> q{0};
    for (int i = 1; i < n; i++) {
        while (q.front() < i - k) q.pop_front();
        from[i] = q.front();
        dp[i] = c[i] + dp[q.front()];
        while (!q.empty() && dp[q.back()] >= dp[i]) q.pop_back();
        q.push_back(i);
    }
    vector<int> lit;
    for (int i = n - 1; i != -1; i = from[i]) lit.push_back(i);   // walk back from the last post
    reverse(lit.begin(), lit.end());
    cout << dp[n - 1] << "\n";
    for (int x : lit) cout << x << " ";
    cout << "\n";
    return 0;
}

Sample 1 prints 14 and then 0 2 5 7. Sample 2 prints 3 and then 0 2 4. 1 1 / 7 prints 7 and then 0.

2. Gap rule: lit posts at least a and at most k apart (input n a k, then the costs; print −1 if it is impossible).

Solution

The window is now i − k ≤ j ≤ i − a. Index j becomes usable exactly when i reaches j + a, so push j = i − a at step i (not i itself). Skip unreachable states, which keep dp = INF.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;

int main() {
    int n, a, k;                              // gap between lit posts: a <= gap <= k
    cin >> n >> a >> k;
    vector<ll> c(n);
    for (ll &x : c) cin >> x;
    vector<ll> dp(n, INF);
    dp[0] = c[0];
    deque<int> q;
    for (int i = 1; i < n; i++) {
        int j = i - a;                         // j becomes usable exactly when i - j = a
        if (j >= 0 && dp[j] < INF) {
            while (!q.empty() && dp[q.back()] >= dp[j]) q.pop_back();
            q.push_back(j);
        }
        while (!q.empty() && q.front() < i - k) q.pop_front();
        if (!q.empty()) dp[i] = c[i] + dp[q.front()];
    }
    cout << (dp[n - 1] >= INF ? -1 : dp[n - 1]) << "\n";
    return 0;
}

8 3 4 / 3 9 4 7 8 2 6 5 prints 15 (posts 0, 3, 7). With a = 1 and k = 3 it prints 14, the original answer. 4 2 2 / 1 1 1 1 prints -1, because post 3 cannot be reached with even gaps.

3. Maximise beauty instead of cost (beauty b[i] may be negative; the same gap ≤ k rule applies).

Solution

This is the mirror image: the deque keeps dp decreasing from front to back, the front is the window maximum, and you pop from the back while dp[back] <= dp[i].

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> b(n);                          // beauty, may be negative
    for (ll &x : b) cin >> x;
    vector<ll> dp(n);
    dp[0] = b[0];
    deque<int> q{0};                          // dp DEcreases front to back
    for (int i = 1; i < n; i++) {
        while (q.front() < i - k) q.pop_front();
        dp[i] = b[i] + dp[q.front()];          // front = window maximum
        while (!q.empty() && dp[q.back()] <= dp[i]) q.pop_back();
        q.push_back(i);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

8 3 / 3 -9 4 -7 -8 2 -6 5 prints 14 (posts 0, 2, 5, 7: 3 + 4 + 2 + 5). 5 2 / 4 -1 -5 3 2 prints 8 (posts 0, 1, 3, 4: 4 − 1 + 3 + 2). If every beauty were positive, you would simply light every post.

4. Sliding-window maximum of an array: print the maximum of every window of k consecutive elements.

Solution

This is the same deque without the DP: indices, with values decreasing front to back.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    deque<int> q;                             // indices, a[] decreasing front to back
    for (int i = 0; i < n; i++) {
        while (!q.empty() && q.front() <= i - k) q.pop_front();   // left the window
        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();   // smaller and older
        q.push_back(i);
        if (i >= k - 1) cout << a[q.front()] << " ";
    }
    cout << "\n";
    return 0;
}

8 3 / 1 3 -1 -3 5 3 6 7 prints 3 3 5 5 6 7. Here the window is i − k + 1 … i and includes i itself, so the expiry test is <= i - k. In the DP, the window ends at i − 1.

Quick quiz

The deque holds dp values 4, 6, 9 (front → back). The new post has dp = 5. After the pops from the back and the push, what does the deque hold?

// pop_back while dp[back] >= 5
// then push 5

A) 4, 6, 9, 5 · B) 4, 5 · C) 5 · D) 4, 5, 6, 9

Answer

B. 9 ≥ 5 and 6 ≥ 5 are popped from the back. 4 < 5 stays. Then 5 is pushed, giving 4, 5. The values still increase from front to back.

Interview questions

  1. What is a sliding-window minimum, and how do you compute it in O(n)? It is the minimum of each block of k consecutive values. Keep a monotonic deque of indices: pop expired indices from the front, pop worse values from the back, and read the front.
  2. Why is the monotonic deque O(n) when it has a while loop inside a for loop? Each index is pushed once and popped at most once, so the total number of pops is at most n. This is amortised O(1) per step.
  3. Why does the deque store indices and not values? To know when an entry has left the window, you need its position. The value is looked up as dp[index].
  4. When is a plain running (prefix) minimum enough? When the window only grows (every window starts at 0), nothing ever leaves, so "minimum so far" is the window minimum.
  5. The transition is min over j of (dp[j] + p · (i − j)). How do you make it O(1)? Separate the terms: p · i + min(dp[j] − p · j). The i-part leaves the min, and the j-part is a fixed value per j that you can keep a prefix minimum (or a deque) of.
  6. Deque or multiset or segment tree for a window minimum? The deque is O(n) and simplest when the window's ends only move forward. A multiset is O(n log n) and also supports arbitrary deletions. A segment tree is O(log n) per query and handles arbitrary ranges and point updates.

Glossary

Term Meaning Example
DP (dynamic programming) Solve a problem by storing answers to smaller subproblems and reusing them dp[0], dp[1], … dp[n − 1]
DP state What one stored value means dp[i] = cheapest plan whose last lit post is i
Transition The formula that computes a state from earlier states dp[i] = c[i] + min dp[j], i − k ≤ j < i
Base case A state you know directly, without a transition dp[0] = c[0]
DP optimisation Same states and answer, but a faster way to compute each transition O(n · k) → O(n)
Sliding window A range of fixed length that moves forward one step at a time j = i − k … i − 1
Window minimum The smallest value inside the current window front of the deque
Running minimum One variable holding the smallest value seen so far best = min(best, dp[i])
Prefix minimum The minimum of the first i values, which is a running minimum right when windows only grow
Prefix-min trick Use a running minimum when the window starts at 0, after moving the i-part out of the min min(dp[j] − p · j) → 16
Deque Double-ended queue: push and pop at both the front and the back in O(1) deque<int> q
Monotonic deque (queue) A deque whose values stay sorted (here increasing) from front to back dp 3, 7, 10
pop_front / pop_back Remove from the front (expired) / from the back (worse) index 0 at i = 4
Amortised analysis Bounding the total cost of all operations, not each one separately ≤ n pops in total → O(n)
Time complexity How the running time grows with the input size O(n · k), O(n log n), O(n)
TLE Time Limit Exceeded: the program is too slow window loop at n = 10^6
WA Wrong Answer: the program finishes but prints the wrong result 8 instead of 14
multiset A sorted container that allows duplicates, with O(log n) insert, erase and min *win.begin()
Overflow A value exceeds its type's range and wraps around int → -1121117184
long long (ll) 64-bit integer, up to about 9.2 · 10^18 500001000000000
Stress test Compare a fast solution with a slow, obviously correct one on many random inputs all 1000 tests passed
Brute force The direct, slow but simple solution the O(n · k) loop
Fast I/O Untie C++ streams from C I/O for fast reading of large input ios::sync_with_stdio(false); cin.tie(nullptr);
Reconstruction Recover the actual choices, not just the optimal value from[i] → 0 2 5 7

Summary

  • dp[i] = c[i] + min of dp over the window i − k … i − 1. The DP is right, and looping over the window is O(n · k), which is TLE at n = 10^6.
  • A running minimum is fast but wrong on a sliding window (8 instead of 14), because it keeps expired posts.
  • The prefix-min trick is right when windows only grow. If the formula mixes i and j, pull the i-part out of the min first (fine variant: 16).
  • Monotonic deque: pop expired indices from the front, read the front, pop worse indices from the back, push i. Every index goes in and out once, so the total is O(n).
  • Before trusting the fast solution, stress-test it against the slow loop (all 1000 tests passed).
  • Sums of up to 10^6 values of size 10^9 need long long; int gives -1121117184.
  • Real outputs: 14, 3, 7, 186608096 (0.05 s) and 500001000000000.

Solutions in C++, Java and Python

Problem R · Lantern Lane

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> c(n);
    for (ll &x : c) cin >> x;
    vector<ll> dp(n);
    dp[0] = c[0];
    deque<int> q;                     // indices; dp increases front to back
    q.push_back(0);
    for (int i = 1; i < n; i++) {
        while (q.front() < i - k) q.pop_front();  // left the window
        dp[i] = c[i] + dp[q.front()];             // front = window minimum
        while (!q.empty() && dp[q.back()] >= dp[i]) q.pop_back();  // useless
        q.push_back(i);
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

Java (fast input with DataInputStream; an int array with two pointers serves as the deque)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = (int) readLong(in), k = (int) readLong(in);
        long[] c = new long[n];
        for (int i = 0; i < n; i++) c[i] = readLong(in);
        long[] dp = new long[n];
        dp[0] = c[0];
        int[] q = new int[n];                      // deque of indices in an array
        int head = 0, tail = 0;                    // q[head .. tail-1]
        q[tail++] = 0;
        for (int i = 1; i < n; i++) {
            while (q[head] < i - k) head++;                              // left the window
            dp[i] = c[i] + dp[q[head]];                                  // front = window minimum
            while (tail > head && dp[q[tail - 1]] >= dp[i]) tail--;      // older and not cheaper
            q[tail++] = i;
        }
        System.out.println(dp[n - 1]);
    }

    static long readLong(DataInputStream in) throws IOException {
        int b = in.read();
        while (b != '-' && (b < '0' || b > '9')) b = in.read();
        boolean neg = b == '-';
        if (neg) b = in.read();
        long x = 0;
        while (b >= '0' && b <= '9') { x = x * 10 + (b - '0'); b = in.read(); }
        return neg ? -x : x;
    }
}

Python (sys.stdin and collections.deque)

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    c = list(map(int, data[2:2 + n]))
    dp = [0] * n
    dp[0] = c[0]
    q = deque([0])                        # indices; dp increases front to back
    for i in range(1, n):
        while q[0] < i - k:               # left the window
            q.popleft()
        dp[i] = c[i] + dp[q[0]]           # front = window minimum
        while q and dp[q[-1]] >= dp[i]:   # older and not cheaper
            q.pop()
        q.append(i)
    print(dp[n - 1])

main()

All three print 14, 3 and 7 on the three samples. On n = 10^6 with every cost 10^9 and k = 2, all three print 500001000000000. On a random file with n = 10^6 and k = 5 · 10^5, all three print 1270587369, Java and Python in under half a second on our machine. Python integers never overflow, and Java uses long.

Next episode: DP optimisation 2: the convex hull trick (when the min over j is the lowest of many lines).