Submission #1264175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264175		goulthen	Džumbus (COCI19_dzumbus)	C++20	0 / 110	16 ms	16192 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; ++i)
#define per(i,a,b) for (int i = a; i >= b; --i)
#define pb push_back

const int MAXN = 1e3 + 10;
const int INF = 1e9 + 10;
int dp[MAXN][MAXN][2], a[MAXN], b[MAXN];
vector<int> g[MAXN];

void dfs(int u, int i = 1, int p = -1) {
	b[i] = a[u];
	for (int &v : g[u]) {
		if (v == p) continue;
		dfs(v,i+1,u);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	int n,m;cin >> n >> m;
	rep(i,1,n) cin >> a[i];
	rep(i,1,m) {
		int u,v;cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}

	int st = 1;
	rep(i,1,n) if (g[i].size() == 1) st = i;
	dfs(st);

	rep(i,0,n) rep(j,1,n) dp[i][j][0] = dp[i][j][1] = INF;
	dp[0][0][0] = 0;
	// 0 -> any i, 1 -> we choose i
	rep(i,1,n) {
		rep(j,0,n) {
			dp[i][j][0] = dp[i-1][j][0];
			if (j > 0) dp[i][j][1] = min(dp[i][j][1],dp[i-1][j-1][1] + b[i]);
			if (i > 1 && j > 1) dp[i][j][1] = min(dp[i][j][1], dp[i-2][j-2][0] + b[i] + b[i-1]);
			dp[i][j][0] = min(dp[i][j][0], dp[i][j][1]);
		}
	}

	int q;cin >> q;

	while (q--) {
		int x, ans = 0;cin >> x;
		per(j,n,1) {
			if (dp[n][j][0] <= x) {
				ans = j;
				break;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30