제출 #1134741

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134741		lopkus	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	1105 ms	196168 KiB

triusis

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int dp[n + 1][5001];
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= 5000; j++) {
            dp[i][j] = n + 1;
        }
    }
    for(int j = 1; j <= k; j++) {
        dp[1][j] = (a[1] != j);
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= 5000; j++) {
            for(int q = 1; q <= 5000; q++) {
                if(j - q <= k) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][q] + (a[i] != j));
                }
            }
        }
    }
    int ans = n + 1;
    for(int i = 1; i <= 5000; i++) {
        ans = min(ans, dp[n][i]);
    }
    cout << ans;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37