제출 #1111848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111848		Pwo	학생 (COCI14_studentsko)	C++17	100 / 100	26 ms	800 KiB

studentsko

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, k; cin >> n >> k;
	int a[n], cpy[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		cpy[i] = a[i];
	}
	
	sort(cpy, cpy + n);
	map<int, int> mp;
	for (int i = 0; i < n; i++)
		mp[cpy[i]] = i / k;
	for (int i = 0; i < n; i++)
		a[i] = mp[a[i]];
		
	int ans = 1;
	int dp[n]{}; dp[0] = 1;
	for (int i = 1; i < n; i++) {
		int mx = 0;
		for (int j = 0; j < i; j++) if (a[j] <= a[i])
			mx = max(mx, dp[j]);
		dp[i] = mx + 1;
		ans = max(ans, dp[i]);
	}

	cout << n - ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10