Submission #1264173

#TimeUsernameProblemLanguageResultExecution timeMemory
1264173goulthenDžumbus (COCI19_dzumbus)C++20
0 / 110
16 ms16192 KiB
#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 (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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...