제출 #1207526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207526		Trn115	파일 삭제 (GA3_delete)	C++20	120 / 120	57 ms	83340 KiB

delete

#include <bits/stdc++.h>

#define fi first
#define se second
#define all(x) x.begin(), x.end()

using namespace std;
using pii = pair<int, int>;

constexpr int inf = 1e9;

int DeletePlan( int N, int M, int K, int *A, int *B) {
	vector<int> val(M);
	for (int i = 0; i < N; ++i) ++val[A[i]];
	vector<vector<int>> g(M);
	for (int i = 1; i < M; ++i) g[B[i]].push_back(i);

	vector<int> sum(M);
	int timer = 0;
	vector<vector<pii>> back(M + 1); // 1-based
	function<void(int)> dfs = [&](int v) {
		sum[v] = val[v];
		int num = ++timer;
		for (int u : g[v]) {
			dfs(u);
			sum[v] += sum[u];
		}
		back[timer].push_back({num, sum[v]});
	};
	dfs(0);

	vector<vector<int>> dp(M + 1, vector<int>(K + 1, inf));
	dp[0][0] = 0;
	for (int i = 1; i <= M; ++i) {
		for (int j = 0; j <= K; ++j) dp[i][j] = dp[i - 1][j];
		for (auto [x, ad] : back[i]) {
			for (int j = ad; j <= K; ++j) {
				dp[i][j] = min(dp[i][j], dp[x - 1][j - ad] + 1);
			}
		}
	}

	int res = inf;
	for (int i = 0; i <= K; ++i) {
		res = min(res, dp[M][i] + K - i);
	}
	return res;
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45