oj.uz

Submission #11383

# Submission time Handle Problem Language Result Execution time Memory
11383 2014-11-26T14:46:03 Z gs14004 파일 삭제 (GA3_delete) C++
120 / 120
 84 ms 118764 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 118764 KB Output is correct
2 Correct 0 ms 118764 KB Output is correct
3 Correct 0 ms 118764 KB Output is correct
4 Correct 0 ms 118764 KB Output is correct
5 Correct 0 ms 118764 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 118764 KB Output is correct
2 Correct 0 ms 118764 KB Output is correct
3 Correct 0 ms 118764 KB Output is correct
4 Correct 0 ms 118764 KB Output is correct
5 Correct 0 ms 118764 KB Output is correct
6 Correct 0 ms 118764 KB Output is correct
7 Correct 0 ms 118764 KB Output is correct
8 Correct 0 ms 118764 KB Output is correct
9 Correct 0 ms 118764 KB Output is correct
10 Correct 0 ms 118764 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 118764 KB Output is correct
2 Correct 0 ms 118764 KB Output is correct
3 Correct 4 ms 118764 KB Output is correct
4 Correct 0 ms 118764 KB Output is correct
5 Correct 0 ms 118764 KB Output is correct
6 Correct 0 ms 118764 KB Output is correct
7 Correct 0 ms 118764 KB Output is correct
8 Correct 0 ms 118764 KB Output is correct
9 Correct 0 ms 118764 KB Output is correct
10 Correct 0 ms 118764 KB Output is correct
11 Correct 0 ms 118764 KB Output is correct
12 Correct 4 ms 118764 KB Output is correct
13 Correct 0 ms 118764 KB Output is correct
14 Correct 0 ms 118764 KB Output is correct
15 Correct 0 ms 118764 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 118764 KB Output is correct
2 Correct 20 ms 118764 KB Output is correct
3 Correct 12 ms 118764 KB Output is correct
4 Correct 32 ms 118764 KB Output is correct
5 Correct 16 ms 118764 KB Output is correct
6 Correct 0 ms 118764 KB Output is correct
7 Correct 0 ms 118764 KB Output is correct
8 Correct 4 ms 118764 KB Output is correct
9 Correct 32 ms 118764 KB Output is correct
10 Correct 12 ms 118764 KB Output is correct
11 Correct 36 ms 118764 KB Output is correct
12 Correct 56 ms 118764 KB Output is correct
13 Correct 52 ms 118764 KB Output is correct
14 Correct 84 ms 118764 KB Output is correct
15 Correct 68 ms 118764 KB Output is correct