oj.uz

Submission #47165

# Submission time Handle Problem Language Result Execution time Memory
47165 2018-04-28T13:18:51 Z Bruteforceman Dostavljač (COCI18_dostavljac) C++11
140 / 140
 150 ms 5560 KB 
#include "bits/stdc++.h"
using namespace std;
vector <int> g[555];
int c[555][555];
int r[555][555];
int dp[2][555][555];
vector <int> child;
const int inf = 1000000000;
const int maxsum = 500;
int a[555];
int sub[555];

void dfs(int x, int par) {
	sub[x] = 1;
	for(auto i : g[x]) {
		if(i == par) continue;
		dfs(i, x);
		sub[x] += sub[i];
	}
	child.clear();
	for(auto i : g[x]) {
		if(i == par) continue;
		child.push_back(i);
	}
	int sz = child.size();
	int cursub = 1;
	// dp[take][i][sum]
	memset(dp, 0, sizeof dp);
	for(int i = 1; i <= (int) child.size(); i++) {
		int xi = child[i-1];
		cursub += sub[xi];
		int sum_range = 3 * cursub;
		int m_range   = 3 * sub[xi];

		for(int take = 0; take <= 1; take++) {
			for(int sum = 0; sum <= sum_range; sum++) {
				dp[take][i][sum] = dp[take][i - 1][sum];
				for(int m = 1; m <= m_range; m++) {
					if(sum - m - 2 >= 0) dp[take][i][sum] = max(dp[take][i][sum], dp[take][i - 1][sum - m - 2] + c[xi][m]);
					if(take == 1 && sum - m - 1 >= 0) dp[take][i][sum] = max(dp[take][i][sum], dp[0][i - 1][sum - m - 1] + r[xi][m]);
				}
			}
		}
	}
	for(int i = 0; i <= maxsum; i++) {
		c[x][i] = dp[0][sz][i];
		if(i > 0) c[x][i] = max(c[x][i], dp[0][sz][i - 1] + a[x]);
		r[x][i] = dp[1][sz][i];
		if(i > 0) r[x][i] = max(r[x][i], dp[1][sz][i - 1] + a[x]);
	}
}

int main(int argc, char const *argv[])
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i < n; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		g[p].push_back(q);
		g[q].push_back(p);
	}
	dfs(1, 0);

	printf("%d\n", r[1][m]);
	return 0;
}

Compilation message

dostavljac.cpp: In function 'int main(int, const char**)':
dostavljac.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
dostavljac.cpp:57:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
                              ~~~~~^~~~~~~~~~~~~
dostavljac.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3004 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3188 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3424 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3516 KB Output is correct
2 Correct 19 ms 3520 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3828 KB Output is correct
2 Correct 27 ms 3832 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3964 KB Output is correct
2 Correct 59 ms 3968 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 4512 KB Output is correct
2 Correct 66 ms 4512 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 5052 KB Output is correct
2 Correct 139 ms 5080 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 5520 KB Output is correct
2 Correct 150 ms 5560 KB Output is correct