Submission #647811

#	Time	Username	Problem	Language	Result	Execution time	Memory
647811		ymm	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	40 ms	5444 KiB

triusis

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;

int fen[N];
void up(int i, int x)
{
	++i;
	while (i < N) {
		fen[i] = min(fen[i], x);
		i += i & -i;
	}
}
int get(int r)
{
	int ans = N;
	while (r) {
		ans = min(ans, fen[r]);
		r -= r & -r;
	}
	return ans;
}

int dp[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, jmp;
	cin >> n >> jmp;
	vector<pii> vec;
	vec.push_back({-jmp*(n+1), ~(n+1)});
	Loop (i,1,n+1) {
		int x;
		cin >> x;
		if (x-jmp*i <= 0)
			vec.push_back({x-jmp*i, ~i});
	}
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	fill(dp, dp+N, N);
	fill(fen, fen+N, N);
	dp[0] = 0;
	up(0, 0);
	for (auto [_, i] : vec) {
		i = ~i;
		dp[i] = get(i) + i - 1;
		up(i, dp[i] - i);
	}
	cout << dp[n+1] << '\n';
}

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