Submission #1278350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278350		cmiuc	Rabbit Carrot (LMIO19_triusis)	C++20	35 / 100	91 ms	98596 KiB

triusis

#include <iostream>

using namespace std;
const int N = 5005;
int dp[N][N], a[N], Ans = N;

int main(){
	int n, m, M = 0;
	cin>>n>>m;

	for (int i=1;i<=n;i++)
		cin>>a[i], M = max(M, a[i]);

	for (int i=0;i<=n;i++){
		for (int j=0;j<=M;j++)
			dp[i][j] = n;
	}

	dp[0][0] = 0;

	for (int i=1;i<=n+1;i++){
		// print(n, M, i-1);
		for (int j=M-1;j>=0;j--)
			dp[i-1][j] = min(dp[i-1][j], dp[i-1][j+1]);

		for (int j=0;j<=M;j++){
			dp[i][j] = dp[i-1][max(0, j - m)] + (a[i] != j);
			if (i == n)
				Ans = min(Ans, dp[i][j]);
		}
	}

	cout<<Ans<<'\n';
}

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