oj.uz

Submission #38455

# Submission time Handle Problem Language Result Execution time Memory
38455 2018-01-04T08:38:04 Z 14kg Biochips (IZhO12_biochips) C++11
100 / 100
 209 ms 399104 KB 
#include <stdio.h>
#include <vector>
#define N 200002
#define INF 2000000000
#define max2(x,y) (x>y?x:y)

using namespace std;
int n, m, dp_lev;
int dp[N][501], in[N];
vector<int> r[N];

void f(int x) {
	int temp = dp_lev;

	for (auto i : r[x]) f(i);

	dp_lev++;
	for (int i = 1; i <= m; i++) dp[dp_lev][i] = max2(dp[dp_lev - 1][i], dp[temp][i - 1] + in[x]);
}
int main() {
	int x;

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &x, &in[i]);
		r[x].push_back(i);
	} 

	for (int i = 1; i <= m; i++) dp[0][i] = -INF;
	f(0), printf("%d", dp[dp_lev][m]);
}

Compilation message

biochips.cpp: In function 'int main()':
biochips.cpp:23:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
biochips.cpp:25:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &in[i]);
                             ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 398048 KB Output is correct
2 Correct 0 ms 398048 KB Output is correct
3 Correct 0 ms 398048 KB Output is correct
4 Correct 16 ms 398180 KB Output is correct
5 Correct 9 ms 398180 KB Output is correct
6 Correct 13 ms 398180 KB Output is correct
7 Correct 153 ms 399104 KB Output is correct
8 Correct 163 ms 399104 KB Output is correct
9 Correct 173 ms 399104 KB Output is correct
10 Correct 209 ms 399104 KB Output is correct