제출 #1283004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283004		paronmanukyan	Dostavljač (COCI18_dostavljac)	C++20	140 / 140	161 ms	2436 KiB

dostavljac

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

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define no_el(x, y) x.find(y) == x.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vct vector
#define vct2dll vct<vct<ll>>
#define vct2dint vct<vct<int>>
#define vct2dchar vct<vct<char>>
#define vct2dbool vct<vct<bool>>
#define vct3dll vct<vct<vct<ll>>>
#define vct3dint vct<vct<vct<int>>>
#define vct3dchar vct<vct<vct<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO                                                                 \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(nullptr);                                                            \
  cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

const int N = 505;
int n, m;
int dp[N][N][2];
int a[N];
vector <int> adj[N];

void dfs(int node, int p) {
    dp[node][1][0] = dp[node][1][1] = a[node];
    dp[node][0][0] = dp[node][0][1] = 0;
    for (auto ch : adj[node]) if (ch != p) {
        dfs(ch, node);
        vct2dint ndp(m + 1, vct<int>(2, 0));
        for (int i = m; i >= 0; --i) {
            for (int j = 0; j <= m; ++j) {
                if (i + j + 1 > m)
                    break;
                ndp[i + j + 1][0] = max(ndp[i + j + 1][0], dp[node][i][1] + dp[ch][j][0]);
                if (i + j + 2 <= m) {
                    ndp[i + j + 2][0] = max(ndp[i + j + 2][0], dp[ch][i][1] + dp[node][j][0]); 
                    ndp[i + j + 2][1] = max(ndp[i + j + 2][1], dp[node][i][1] + dp[ch][j][1]);
                }
            }
        }
        for (int i = 1; i <= m; ++i) 
            dp[node][i][1] = max(dp[node][i][1], ndp[i][1]), 
            dp[node][i][0] = max(dp[node][i][0], ndp[i][0]);
    }
}

int main()
{
	FASTIO
	cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    dfs(1, 0);

    cout << max(dp[1][m][0], dp[1][m][1]) << "\n";
}

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