Submission #479671

#	Time	Username	Problem	Language	Result	Execution time	Memory
479671		AboAlmanal	Financial Report (JOI21_financial)	C++14	48 / 100	1762 ms	298224 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 7000 + 9;
const int INF = (int) 1e9;

int A[N], dp[N][N], pre[N], suff[N];
deque <int> dq[N];
map <int, int> id;

int main () {
	int n;
	cin >> n;
	
	int D;
	cin >> D;
	
	set <int> s;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		s.insert (A[i]);
	}
	
	int c = 1;
	for (auto u: s)
		id[u] = c++;
	
	for (int i = 1; i <= n; i++) {
		A[i] = id[A[i]];
		suff[i] = pre[i] = -INF;
	}
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = -INF;
	
	pre[0] = suff[0] = -INF;
	for (int i = 1; i <= n; i++) {
		
		dp[i][A[i]] = max (1, pre[A[i] - 1] + 1);
		for (int mx = A[i]; mx <= n; mx++) {
			dp[i][mx] = max (dp[i][mx], suff[mx]);
			//dp[i][mx] = max (dp[i][mx], pre[mx]);	
			
			while (dq[mx].size() && dp[dq[mx].back()][mx] < dp[i][mx]) 
				dq[mx].pop_back();
			
			dq[mx].push_back (i);
		}
		
		for (int mx = 1; mx <= n; mx++) {
			while (dq[mx].size() && dq[mx].front() <= i - D) 
				dq[mx].pop_front();
				
			if (dq[mx].size()) {
				pre[mx] = suff[mx] = dp[dq[mx].front()][mx];
			} else {
				pre[mx] = suff[mx] = -INF;
			}
		}
		
		for (int mx = 2; mx <= n; mx++)
			pre[mx] = max (pre[mx], pre[mx - 1]);
			
		//for (int mx = n - 1; mx >= 1; mx--)
			//suff[mx] = max (suff[mx], suff[mx + 1]);
			
			
	}
	
	int res = 1;
	for (int i = 1; i <= n; i++)
		res = max (res, dp[n][i]);
		
	cout << res << "\n";
	return 0;
}

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