Submission #519129

#	Time	Username	Problem	Language	Result	Execution time	Memory
519129		blue	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	57 ms	5356 KiB

triusis

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

using vi = vector<int>;

vi A;
int N, M;

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

	cin >> N >> M;

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


	vi I(1+N);
	for(int i = 0; i <= N; i++) I[i] = i+1;
	sort(I.begin(), I.end(), [] (int l, int r)
	{
		if(A[l] - M*l == A[r] - M*r) return l < r;
		else return A[l] - M*l > A[r] - M*r;
	});

	vi DP(1+N+1, 5'000'000);

	vi BIT(1+N+1, 5'000'000);

	int ans = 5'000'000;

	for(int i: I)
	{
		if(i == 1)
			DP[i] = 0;
		else
		{
			for(int x = i-1; x >= 1; x -= x&-x)
			{
				DP[i] = min(DP[i], BIT[x] + i-1);
			}
		}

		for(int x = i; x <= N+1; x += x&-x)
			BIT[x] = min(BIT[x], DP[i] - i);

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

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

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