Submission #4879

#	Time	Username	Problem	Language	Result	Execution time	Memory
4879		Qwaz	파일 삭제 (GA3_delete)	C++98	120 / 120	56 ms	119540 KiB

delete

#include <cstdio>
#include <vector>

using namespace std;
const int MAX=3020, MAX_N=10020, INF=MAX_N;

int n, m, target, p[MAX], cnt[MAX];
vector < int > children[MAX];

void input(int N, int M, int K, int *A, int *B){
	n = N;
	m = M;
	target = K;

	int i;
	for(i=0; i<n; i++)
		cnt[A[i]]++;

	for(i=0; i<m; i++){
		p[i] = B[i];
		if(i > 0) children[p[i]].push_back(i);
	}
}

int s[MAX], e[MAX], endNum[MAX], index=1;

void numbering(int now){
	s[now] = index;

	int i;
	for(i=0; i<children[now].size(); i++){
		numbering(children[now][i]);
		cnt[now] += cnt[children[now][i]];
	}

	e[now] = index;
	endNum[index] = now;
	index++;
}

int dp[MAX][MAX_N];

int DeletePlan(int N, int M, int K, int *A, int *B){
	input(N, M, K, A, B);

	numbering(0);

	int i, j;
	for(i=1; i<=target; i++)
		dp[0][i] = INF;

	for(i=1; i<index; i++){
		int now = endNum[i];
		for(j=0; j<=target; j++){
			dp[i][j] = dp[i-1][j];
			if(j >= cnt[now] && dp[i][j] > dp[s[now]-1][j-cnt[now]]+1)
				dp[i][j] = dp[s[now]-1][j-cnt[now]]+1;
		}
	}

	int res=INF;
	for(i=0; i<=target; i++)
		res = min(res, dp[index-1][i]+(target-i));

	return res;
}

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