oj.uz

Submission #57585

# Submission time Handle Problem Language Result Execution time Memory
57585 2018-07-15T10:49:25 Z polyfish Dostavljač (COCI18_dostavljac) C++14
140 / 140
 212 ms 28436 KB 
//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 502;
const int INF = 1e9;

int n, m, a[MAX_N], tr_size[MAX_N];
vector<int> f[MAX_N][MAX_N][2];
vector<int> g[MAX_N];

void enter() {
	cin >> n >> m;
	for (int i=1; i<=n; ++i)
		cin >> a[i];
	g[1].push_back(0);
	for (int i=1; i<n; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
}

int fix_root(int u, int par) {
	tr_size[u] = 1;
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i];
		if (v==par) {
			swap(g[u][0], g[u][i]);
		}
		else {
			tr_size[u] += fix_root(v, u);
		}
	}
	return tr_size[u];
}

void init_dp() {
	for (int u=1; u<=n; ++u)
		for (int i=0; i<=m; ++i)
			for (int j=0; j<2; ++j)
				f[u][i][j].resize(g[u].size(), -1);
}

int dp(int u, int total_time, bool come_back, int child_id) {
	if (total_time<0) {
		return -INF;
	}
	if (child_id == 0) {
		return 0;
	}
	if (child_id == g[u].size()) {
		return max(dp(u, total_time, come_back, child_id-1),
					dp(u, total_time-1, come_back, child_id-1) + a[u]);
	}
	if (f[u][total_time][come_back][child_id]!=-1)
		return f[u][total_time][come_back][child_id];
	int res = dp(u, total_time, come_back, child_id - 1);
	int v = g[u][child_id];
	for (int time_for_v=1; time_for_v<=min(3*tr_size[v], total_time); ++time_for_v) {
		res = max(res, dp(u, total_time-time_for_v-2, come_back, child_id-1)
						+ dp(v, time_for_v, true, g[v].size()));
		if (!come_back) {
			res = max(res, dp(u, total_time-time_for_v-1, true, child_id-1)
							+ dp(v, time_for_v, false, g[v].size()));
		}
	}
	return f[u][total_time][come_back][child_id] = res;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	fix_root(1, 0);
	//PR0(g[1], g[1].size());
	//PR(tr_size, n);
	init_dp();
	//debug(dp(1, 1, false, 1));
	cout << dp(1, m, false, g[1].size());
}

Compilation message

dostavljac.cpp: In function 'int fix_root(int, int)':
dostavljac.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
dostavljac.cpp: In function 'int dp(int, int, bool, int)':
dostavljac.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (child_id == g[u].size()) {
      ~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12152 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12392 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12580 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12580 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 13544 KB Output is correct
2 Correct 28 ms 13544 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13544 KB Output is correct
2 Correct 39 ms 15724 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 17600 KB Output is correct
2 Correct 143 ms 17600 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 17600 KB Output is correct
2 Correct 130 ms 22560 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 22620 KB Output is correct
2 Correct 202 ms 22620 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 28436 KB Output is correct
2 Correct 69 ms 28436 KB Output is correct