Submission #768487

#	Time	Username	Problem	Language	Result	Execution time	Memory
768487		jmyszka2007	Financial Report (JOI21_financial)	C++17	0 / 100	4062 ms	4736 KiB

Main

#include <bits/stdc++.h>
using namespace std;
constexpr int LIM = 300'000;
int dp[LIM + 10];
int tab[LIM + 10];
int ran[LIM + 10];
int main() {
	int n, d;
	cin >> n >> d;
	for(int i = 1; i <= n; i++) {
		cin >> tab[i];
	}
	for(int i = 1; i <= n; i++) {
		int akt = i;
		for(int j = i + 1; j <= n; j++) {
			if(j - akt > d) {
				break;
			}
			if(tab[j] <= tab[i]) {
				akt = j;
			}
			ran[i] = j;
		}
	}
	for(int i = 1; i <= n; i++) {
		dp[i] = 1;
		for(int j = i - 1; j >= 1; j--) {
			if(tab[j] < tab[i] && ran[j] >= i) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	int ans = 0;
	for(int j = 1; j <= n; j++) {
		if(ran[j] == n) {
			ans = max(ans, dp[j]);
		}
	}
	cout << ans << '\n';
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35