Submission #4208

#	Time	Username	Problem	Language	Result	Execution time	Memory
4208		cki86201	파일 삭제 (GA3_delete)	C++98	120 / 120	80 ms	119664 KiB

delete

#include<algorithm>
#include<string.h>
using namespace std;
int Dp[3030][10010];
int R[3030],L[3030],tot[3030];
int st[3030],en[6060];
short next[6060];
bool check[3030];
int ord[3030],co;
int now,sum;

void dfs(int x)
{
	check[x]=1;
	L[x]=now;
	for(int i=st[x];i;i=next[i]){
		if(!check[en[i]]){dfs(en[i]);tot[x]+=tot[en[i]];}
	}
	ord[++co]=now=x;
}

void addedge(int s,int d,int c)
{
	next[c]=st[s];
	st[s]=c;
	en[c]=d;
}

int DeletePlan( int M, int N, int K, int *A, int *B){
	int i;
	for(i=0;i<M;i++){R[A[i]]++;tot[A[i]]++;}
	for(i=1;i<N;i++){
		addedge(i,B[i],2*i);
		addedge(B[i],i,2*i+1);
	}
	dfs(0);
	memset(Dp,1,sizeof(Dp));
	Dp[0][0]=0;
	for(i=1;i<=N;i++){
		int x=ord[i],j;
		for(j=0;j<=sum;j++)Dp[x][j]=Dp[ord[i-1]][j];
		for(j=sum+1;j<=sum+R[x];j++)Dp[x][j]=Dp[x][j-1]+1;
		for(j=sum+R[x];j>=tot[x];j--){
			Dp[x][j]=min(Dp[x][j],Dp[L[x]][j-tot[x]]+1);
		}
		sum+=R[x];
	}
	return Dp[0][K];
}

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