oj.uz

Submission #57583

# Submission time Handle Problem Language Result Execution time Memory
57583 2018-07-15T10:02:34 Z polyfish Dostavljač (COCI18_dostavljac) C++14
98 / 140
 2000 ms 28676 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];
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);
	}
}

void fix_root(int u, int par) {
	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
			fix_root(v, 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<=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());
	init_dp();
	//debug(dp(1, 1, false, 1));
	cout << dp(1, m, false, g[1].size());
}

Compilation message

dostavljac.cpp: In function 'void fix_root(int, int)':
dostavljac.cpp:32: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:55: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 14 ms 12280 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12728 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12728 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 13744 KB Output is correct
2 Correct 50 ms 13744 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13744 KB Output is correct
2 Correct 713 ms 16020 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1376 ms 17764 KB Output is correct
2 Correct 380 ms 17764 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 17764 KB Output is correct
2 Execution timed out 2045 ms 22756 KB Time limit exceeded

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 22780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2031 ms 28676 KB Time limit exceeded
2 Halted 0 ms 0 KB -