Submission #222009

#	Time	Username	Problem	Language	Result	Execution time	Memory
222009		ZwariowanyMarcin	Dostavljač (COCI18_dostavljac)	C++17	126 / 140	2080 ms	3704 KiB

dostavljac

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define sz(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
#define cint int&
 
using namespace std;

const int nax = 505;

void maxi(int &a, int b) {
	a = max(a, b);
}

int n, m;
int a, b;
int cost[nax];
vector <int> g[nax];

int dp[nax][nax][2][2];
int dp2[nax][2][2];

// 0 to musze wrocic -> 0
// 1 to nie musze -> 0 / 1

void dfs(int v, int p) {
	rep(i, 0, m)
		rep(a, 0, 1)
			rep(b, 0, 1)
				dp[v][i][a][b] = -1e9;
	dp[v][0][0][0] = 0;
	dp[v][0][1][0] = 0;
	dp[v][1][0][0] = cost[v];
	dp[v][1][1][0] = cost[v]; 
	
	for (auto it : g[v]) {
		if (it == p) continue;
		
		dfs(it, v);
		
		rep(i, 0, m)
			rep(a, 0, 1)
				rep(b, 0, 1)
					dp2[i][a][b] = dp[v][i][a][b];
		
		rep(i, 0, m)
			rep(j, 0, m - i)
				rep(a, 0, 1)
					rep(b, 0, 1) {
						if (a == 0 && b == 1) continue;
						rep(c, 0, 1) {
							if (a == 0 && c == 1) continue;
							rep(d, 0, 1) {
								if (c == 0 && d == 1) continue;
								if (a == 1 && b == 1 && c == 1) continue;
								if (a == 0 && c == 0) {
									int s = i + j + 2;
									if (s <= m) maxi(dp2[s][0][0], dp[v][i][a][b] + dp[it][j][c][d]);
								}
								if (a == 1) {
									int e = (b | c);
									int s = i + j + 1 + !(c == 1);
									if (s <= m) maxi(dp2[s][1][e], dp[v][i][a][b] + dp[it][j][c][d]);
								}
							}
						}
					}
		rep(i, 0, m)
			rep(a, 0, 1)
				rep(b, 0, 1)
					dp[v][i][a][b] = dp2[i][a][b];
		}
}

int main() {		
	scanf ("%d%d", &n, &m);
	rep(i, 1, n) scanf ("%d", cost + i);
	rep(i, 1, n - 1) {
		scanf ("%d%d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}	
	dfs(1, 0);
	int res = 0;
	rep(i, 0, m)
		rep(a, 0, 1)
			rep(b, 0, 1)
				maxi(res, dp[1][i][a][b]);
	printf ("%d\n", res);
	
	return 0;
}

Compilation message (stderr)

dostavljac.cpp: In function 'int main()':
dostavljac.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &m);
  ~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:85:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 1, n) scanf ("%d", cost + i);
               ~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:87:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~

• 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: 0 / 14