제출 #727176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727176		NeroZein	Financial Report (JOI21_financial)	C++17	33 / 100	185 ms	265324 KiB

Main

#include "bits/stdc++.h"
using namespace std;
 
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
 
const int N = 405;
const int M = 300005;
 
int a[M];
int seg[M << 1];
 
int n, d;
int dp[N][N][N]; 
int bt (int id, int mx, int la) {
	if (id == n) return 0; 
	int& ret = dp[id][mx][la];
	if (ret != -1) {
		return ret;
	}
	if (id - la > d && mx != 0) return 0; 
	ret = max(bt(id + 1, mx, la), bt(id + 1, max(mx, a[id]), id) + (int) (a[id] > mx));
	return ret;
}
 
int get (int nd, int l, int r, int s, int e) {
	if (l >= s && r <= e) return seg[nd]; 
	int mid = (l + r) >> 1;
	int rs = nd + ((mid - l + 1) << 1); 
	if (mid >= e) {
		return get(nd + 1, l, mid, s, e);
	} else {
		if (mid < s) {
			return get(rs, mid + 1, r, s, e); 
		} else {
			return max(get(rs, mid + 1, r, s, e), get(nd + 1, l, mid, s, e));
		}
	}
}
int get (int v, int e) {
	if (v > e) return 0; 
	return get(0, 0, n, v, e);
}

void upd (int nd, int l, int r, int p, int v) {
	if (l == r) return void(seg[nd] = max(seg[nd], v)); 
	int mid = (l + r) >> 1;
	int rs = nd + ((mid - l + 1) << 1);
	if (p <= mid) {
		upd(nd + 1, l, mid, p, v);
	} else {
		upd(rs, mid + 1, r, p, v); 
	}
	seg[nd] = max(seg[nd + 1], seg[rs]); 
}
void upd (int p, int v) {
	upd(0, 0, n, p, v); 
}
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> d;
	vector<int> b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b.begin(), b.end());
	b.resize(unique(b.begin(), b.end()) - b.begin());
	for (int i = 0; i < n; ++i) {
		a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1; 
	}
	if (d < n) {
		memset(dp, -1, sizeof dp);
		cout << bt(0, 0, 0) << '\n';
		return 0; 		
	}
	int ans = 1; 
	for (int i = n - 1; i >= 0; --i) {
		int tmp = get(a[i] + 1, n) + 1;
		upd(a[i], tmp);
		ans = max(ans, tmp); 
	}
	cout << ans << '\n';
	return 0;
}

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