Submission #519123

#	Time	Username	Problem	Language	Result	Execution time	Memory
519123		blue	Rabbit Carrot (LMIO19_triusis)	C++17	63 / 100	1032 ms	2232 KiB

triusis

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

using vi = vector<int>;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	vi A(1+N);
	A[0] = 0;
	for(int i = 1; i <= N; i++) cin >> A[i];

	vi DP(1+N, 2*N);

	DP[0] = 0;

	int ans = N;

	for(int i = 1; i <= N; i++)
	{
		for(int j = 0; j < i; j++)
		{
			if(A[i] - A[j] <= M * (i - j))
			{
				DP[i] = min(DP[i], DP[j] + (i-1-j));
			}
		}

		ans = min(ans, DP[i] + N-i);

		// cerr << i << " : " << DP[i] << '\n';
	}

	cout << ans << '\n';
}

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