Submission #47165

#	Time	Username	Problem	Language	Result	Execution time	Memory
47165		Bruteforceman	Dostavljač (COCI18_dostavljac)	C++11	140 / 140	150 ms	5560 KiB

dostavljac

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14