Submission #4198

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4198	2013-09-05T03:50:38 Z	cki86201	파일 삭제 (GA3_delete)	C++	85 / 120	48 ms	119664 KB

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=tot[x];k>tot[en[j]];k--){
				Dp[x][k]=min(Dp[x][k],Dp[x][k-tot[en[j]]]+1);
			}
			for(k=0;k<=tot[en[j]];k++){
				Dp[x][k]=min(Dp[x][k],Dp[en[j]][k]);
			}
		}
	}
	return Dp[0][K];
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	119664 KB	Output is correct
2	Correct	28 ms	119664 KB	Output is correct
3	Correct	24 ms	119664 KB	Output is correct
4	Correct	24 ms	119664 KB	Output is correct
5	Correct	12 ms	119664 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	119664 KB	Output is correct
2	Correct	16 ms	119664 KB	Output is correct
3	Correct	16 ms	119664 KB	Output is correct
4	Correct	20 ms	119664 KB	Output is correct
5	Correct	20 ms	119664 KB	Output is correct
6	Correct	20 ms	119664 KB	Output is correct
7	Correct	28 ms	119664 KB	Output is correct
8	Correct	24 ms	119664 KB	Output is correct
9	Correct	24 ms	119664 KB	Output is correct
10	Correct	16 ms	119664 KB	Output is correct

Subtask #3

0.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	119664 KB	Output is correct
2	Incorrect	48 ms	119664 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	119664 KB	Output is correct
2	Correct	28 ms	119664 KB	Output is correct
3	Correct	20 ms	119664 KB	Output is correct
4	Correct	28 ms	119664 KB	Output is correct
5	Correct	36 ms	119664 KB	Output is correct
6	Correct	28 ms	119664 KB	Output is correct
7	Correct	40 ms	119664 KB	Output is correct
8	Correct	24 ms	119664 KB	Output is correct
9	Correct	40 ms	119664 KB	Output is correct
10	Correct	40 ms	119664 KB	Output is correct
11	Correct	36 ms	119664 KB	Output is correct
12	Correct	40 ms	119664 KB	Output is correct
13	Correct	36 ms	119664 KB	Output is correct
14	Correct	40 ms	119664 KB	Output is correct
15	Correct	20 ms	119664 KB	Output is correct