#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];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
119664 KB |
Output is correct |
| 2 |
Correct |
32 ms |
119664 KB |
Output is correct |
| 3 |
Correct |
28 ms |
119664 KB |
Output is correct |
| 4 |
Correct |
36 ms |
119664 KB |
Output is correct |
| 5 |
Correct |
16 ms |
119664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
119664 KB |
Output is correct |
| 2 |
Correct |
12 ms |
119664 KB |
Output is correct |
| 3 |
Correct |
32 ms |
119664 KB |
Output is correct |
| 4 |
Correct |
20 ms |
119664 KB |
Output is correct |
| 5 |
Correct |
32 ms |
119664 KB |
Output is correct |
| 6 |
Correct |
36 ms |
119664 KB |
Output is correct |
| 7 |
Correct |
16 ms |
119664 KB |
Output is correct |
| 8 |
Correct |
16 ms |
119664 KB |
Output is correct |
| 9 |
Correct |
16 ms |
119664 KB |
Output is correct |
| 10 |
Correct |
20 ms |
119664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
119664 KB |
Output is correct |
| 2 |
Correct |
52 ms |
119664 KB |
Output is correct |
| 3 |
Correct |
28 ms |
119664 KB |
Output is correct |
| 4 |
Correct |
32 ms |
119664 KB |
Output is correct |
| 5 |
Correct |
20 ms |
119664 KB |
Output is correct |
| 6 |
Correct |
24 ms |
119664 KB |
Output is correct |
| 7 |
Correct |
12 ms |
119664 KB |
Output is correct |
| 8 |
Correct |
32 ms |
119664 KB |
Output is correct |
| 9 |
Correct |
28 ms |
119664 KB |
Output is correct |
| 10 |
Correct |
32 ms |
119664 KB |
Output is correct |
| 11 |
Correct |
24 ms |
119664 KB |
Output is correct |
| 12 |
Correct |
20 ms |
119664 KB |
Output is correct |
| 13 |
Correct |
28 ms |
119664 KB |
Output is correct |
| 14 |
Correct |
20 ms |
119664 KB |
Output is correct |
| 15 |
Correct |
28 ms |
119664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
119664 KB |
Output is correct |
| 2 |
Correct |
44 ms |
119664 KB |
Output is correct |
| 3 |
Correct |
40 ms |
119664 KB |
Output is correct |
| 4 |
Correct |
44 ms |
119664 KB |
Output is correct |
| 5 |
Correct |
40 ms |
119664 KB |
Output is correct |
| 6 |
Correct |
44 ms |
119664 KB |
Output is correct |
| 7 |
Correct |
32 ms |
119664 KB |
Output is correct |
| 8 |
Correct |
48 ms |
119664 KB |
Output is correct |
| 9 |
Correct |
32 ms |
119664 KB |
Output is correct |
| 10 |
Correct |
56 ms |
119664 KB |
Output is correct |
| 11 |
Correct |
68 ms |
119664 KB |
Output is correct |
| 12 |
Correct |
56 ms |
119664 KB |
Output is correct |
| 13 |
Correct |
56 ms |
119664 KB |
Output is correct |
| 14 |
Correct |
80 ms |
119664 KB |
Output is correct |
| 15 |
Correct |
60 ms |
119664 KB |
Output is correct |
