oj.uz

답안 #86914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
86914 2018-11-28T13:38:57 Z Just_Solve_The_Problem 바이오칩 (IZhO12_biochips) C++11
100 / 100
 820 ms 409476 KB 
#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

const int N = (int)2e5 + 7;
const int M = (int)500 + 7;

int n, m;
int pr[N], w[N];
vector < int > gr[N];
vector < int > order;
int tiktak;
int tin[N], tout[N];
int dp[N][M];

void dfs(int v) {
	if (gr[v].empty()) tiktak++;
	tin[v] = tiktak;
	for (int to : gr[v]) {
		dfs(to);
	}
	order.push_back(v);
	tout[v] = tiktak;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> pr[i] >> w[i];
		gr[pr[i]].push_back(i);
	}
	dfs(gr[0][0]);
	for (int i = 0; i < n; i++) {
		int v = order[i];
		int l = tin[v];
		int r = tout[v];
		for (int j = 0; j <= m; j++) {
			dp[r][j] = max(dp[r][j], dp[r - 1][j]);
		}
		for (int j = 1; j <= min(l, m); j++) {
			dp[r][j] = max(dp[r][j], dp[l - 1][j - 1] + w[v]);
		}
	}
	int res = 0;
	for (int i = 1; i <= tiktak; i++) {
		res = max(res, dp[i][m]);
	}
	cout << res;
}

Compilation message

biochips.cpp:28:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5116 KB Output is correct
2 Correct 7 ms 5244 KB Output is correct
3 Correct 7 ms 5316 KB Output is correct
4 Correct 23 ms 14580 KB Output is correct
5 Correct 28 ms 19088 KB Output is correct
6 Correct 27 ms 19192 KB Output is correct
7 Correct 549 ms 302892 KB Output is correct
8 Correct 535 ms 304444 KB Output is correct
9 Correct 703 ms 370012 KB Output is correct
10 Correct 820 ms 409476 KB Output is correct