Submission #11383

#	Time	Username	Problem	Language	Result	Execution time	Memory
11383		gs14004	파일 삭제 (GA3_delete)	C++98	120 / 120	84 ms	118764 KiB

delete

#include <algorithm>
#include <vector>
using namespace std;

int n,m,k;
int size[3005], cap[3005], pcap[3005];
vector<int> graph[3005];
int dp[3005][10005];
int dfn[3005], piv;

int dfs(int x){
    dfn[x] = piv++;
    int pos = dfn[x];
    cap[pos] = pcap[x];
    size[pos] = 1;
    for (int i=0; i<graph[x].size(); i++) {
        cap[pos] += dfs(graph[x][i]);
        size[pos] += size[dfn[graph[x][i]]];
    }
    return cap[pos];
}

int DeletePlan( int N, int M, int K, int *A, int *B) {
    n = N, m = M, k = K;
    for (int i=0; i<n; i++) {
        pcap[A[i]]++;
    }
    for (int i=0; i<m; i++) {
        if(B[i] != -1) graph[B[i]].push_back(i);
    }
    dfs(0);
    for (int i=m; i>=0; i--) {
        for (int j=0; j<=k; j++) {
            if(i == m) dp[i][j] = j;
            else if(size[i] != 0 && j >= cap[i]) dp[i][j] = min(dp[i+1][j],dp[i + size[i]][j - cap[i]] + 1);
            else dp[i][j] = dp[i+1][j];
        }
    }
	return dp[0][k];
}

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