제출 #517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
517		tncks0121	파일 삭제 (GA3_delete)	C++98	120 / 120	36 ms	118912 KiB

delete

#include<vector>
#define INF 999999999
using namespace std;
vector<int>E[10001];
int D[3001][10001],ren[10001],p[10001],c,C[10001],C2[10001],TP[10001],bef[10001];
void DFS(int a){
    int i,t=c;
	for(i=0;i<E[a].size();i++){
		DFS(E[a][i]);
		TP[a]+=TP[E[a][i]];
	}
	ren[a]=++c;
	bef[c]=t;
}
int DeletePlan( int N, int M, int K, int *A, int *B) {
	int i,j,S,t;
	for(i=1;i<M;i++){
		E[B[i]].push_back(i);
	}
	for(i=0;i<N;i++)TP[A[i]]++;
	DFS(0);
	for(i=0;i<M;i++)C[ren[i]]=TP[i];
	for(i=0;i<N;i++)C2[ren[A[i]]]++;
	S=0;
	for(j=1;j<=K;j++)D[0][j]=INF;
	for(i=1;i<=M;i++){
		for(j=1;j<=S;j++)D[i][j]=D[i-1][j];
		for(j=S+1;j<=S+C2[i]&&j<=K;j++)D[i][j]=D[i-1][S]+j-S;
		S+=C2[i];if(S>K)S=K;
		for(j=S-C[i];j>=0;j--){
			D[i][j+C[i]]=min(D[i][j+C[i]],D[bef[i]][j]+1);
		}
	}
	return D[M][K];
}

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