Submission #4197

#	Time	Username	Problem	Language	Result	Execution time	Memory
4197		cki86201	파일 삭제 (GA3_delete)	C++98	15 / 120	48 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;

void dfs(int x)
{
	check[x]=1;
	for(int i=st[x];i;i=next[i]){
		if(!check[en[i]]){dfs(en[i]);tot[x]+=tot[en[i]];}
	}
	ord[++co]=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));
	for(i=1;i<=N;i++){
		int x=ord[i];
		if(x==0){
			x++;
			x--;
		}
		Dp[x][0]=0;
		int j,k;
		for(j=1;j<tot[x];j++)Dp[x][j]=j;
		Dp[x][tot[x]]=1;
		for(j=st[x];j;j=next[j]){
			if(B[x]==en[j])continue;
			for(k=0;k<=tot[en[j]];k++){
				Dp[x][k]=min(Dp[x][k],Dp[en[j]][k]);
			}
			for(k=tot[en[j]];k<=tot[x];k++){
				Dp[x][k]=min(Dp[x][k],Dp[en[j]][k-tot[en[j]]]+1);
			}
		}
		for(k=tot[x]-R[x]+1;k<tot[x];k++){
			Dp[x][k]=Dp[x][k-1]+1;
		}
	}
	return Dp[0][K];
}

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