# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
85251 | 2018-11-19T01:50:03 Z | zoooma13 | 바이오칩 (IZhO12_biochips) | C++14 | 2000 ms | 6788 KB |
#include <bits/stdc++.h> using namespace std; #define MAX_N 200005 #define MAX_M 502 #define INF 0x3f3f3f3f int N ,M; int A ,B; int Mem[MAX_N]; vector <int> Adj[MAX_N]; int dp[MAX_M]; void Solve(int v) { int dp_new[M+1] = {0} ,dp_all[M+1] = {0}; for(int i : Adj[v]) { Solve(i); for(int j=1; j<=M; j++) for(int k=0; k<=M-j; k++) dp_new[j+k] = max(dp_new[j+k] ,dp_all[k] + dp[j]); for(int k=0; k<=M; k++) dp_all[k] = max(dp_all[k] ,dp_new[k]); } for(int l=0; l<=M; l++) dp[l] = dp_all[l]; dp[1] = max(dp[1] ,Mem[v]); } int main() { scanf("%d%d",&N,&M); assert(N < MAX_N && M < MAX_M); int root; for(int i=1; i<=N; i++) { scanf("%d%d",&A,&B); Mem[i] = B; if(A == 0) root = i; else Adj[A].push_back(i); } Solve(root); printf("%d\n",dp[M]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 5236 KB | Output is correct |
3 | Correct | 6 ms | 5236 KB | Output is correct |
4 | Correct | 31 ms | 5472 KB | Output is correct |
5 | Correct | 44 ms | 5472 KB | Output is correct |
6 | Correct | 67 ms | 5472 KB | Output is correct |
7 | Execution timed out | 2068 ms | 6788 KB | Time limit exceeded |
8 | Halted | 0 ms | 0 KB | - |