Submission #340048

#	Time	Username	Problem	Language	Result	Execution time	Memory
340048		sinamhdv	Džumbus (COCI19_dzumbus)	C++11	110 / 110	177 ms	47340 KiB

dzumbus

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 1100

int n, m;
vector<int> adj[MAXN];
ll dp[3][MAXN][MAXN];
int D[MAXN];
int par[MAXN];
int subtree[MAXN];

ll mdp[MAXN][MAXN];
ll ans[MAXN][MAXN];

void dfs(int v)
{
	subtree[v] = 1;
	
	// dp base
	dp[1][v][0] = D[v];
	dp[0][v][0] = 0;

	bool fr = true;

	for (int u : adj[v])
	{
		if (u == par[v])
		{
			continue;
		}
		par[u] = v;
		dfs(u);

		if (fr)
		{
			for (int i = subtree[u] + 1; i >= 2; i--)
			{
				dp[2][v][i] = min(dp[2][v][i], min(dp[2][u][i - 1], dp[1][u][i - 2]) + D[v]);
				dp[1][v][i] = min(dp[1][v][i], dp[0][u][i] + D[v]);
				dp[0][v][i] = min(dp[0][v][i], min(dp[0][u][i], min(dp[1][u][i], dp[2][u][i])));
			}
			fr = false;
			subtree[v] += subtree[u];
			continue;
		}
		
		// update dp[2]
		for (int i = subtree[v]; i >= 1; i--)
		{
			for (int j = subtree[u]; j >= 1; j--)
			{
				ll nw = min(dp[2][v][i] + min(dp[0][u][j], min(dp[1][u][j - 1], dp[2][u][j])), \
							dp[1][v][i - 1] + min(dp[1][u][j - 1], dp[2][u][j]));
				dp[2][v][i + j] = min(dp[2][v][i + j], nw);
			}
		}

		// update dp[1] & dp[0]
		for (int i = subtree[v]; i >= 0; i--)
		{
			for (int j = subtree[u]; j >= 0; j--)
			{
				dp[1][v][i + j] = min(dp[1][v][i + j], dp[1][v][i] + dp[0][u][j]);
				dp[0][v][i + j] = min(dp[0][v][i + j], dp[0][v][i] + min(dp[0][u][j], min(dp[1][u][j], dp[2][u][j])));
			}
		}

		subtree[v] += subtree[u];
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m;
	FOR(i, 1, n + 1)
	{
		cin >> D[i];
	}
	FOR(i, 0, m)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	// fill dp
	FOR(i, 0, 3)
	{
		FOR(j, 0, MAXN)
		{
			fill(dp[i][j], dp[i][j] + MAXN, LINF);
		}
	}

	vector<int> rt;
	FOR(i, 1, n + 1)
	{
		if (!par[i])
		{
			par[i] = -1;
			dfs(i);
			rt.pb(i);
		}
	}
	FOR(i, 1, n + 1)
	{
		FOR(j, 0, subtree[i] + 1)
		{
			mdp[i][j] = min(dp[0][i][j], min(dp[1][i][j], dp[2][i][j]));
		}
	}

	/*
	FOR(i, 1, n + 1)
	{
		FOR(j, 0, subtree[i] + 1)
		{
			FOR(k, 0, 3)
			{
				cout << "dp[" << k << "][" << i << "][" << j << "]: " << dp[k][i][j] << endl;
			}
		}
	}
	*/
	

	
	dbgr(rt.begin(), rt.end());


	FOR(i, 0, MAXN)
	{
		fill(ans[i], ans[i] + MAXN, LINF);
	}

	ans[0][0] = 0;
	FOR(i, 1, (int)rt.size() + 1)
	{
		ans[i][0] = 0;
		FOR(j, 1, n + 1)
		{
			FOR(k, 0, min(subtree[rt[i - 1]], j) + 1)
			{
				ans[i][j] = min(ans[i][j], ans[i - 1][j - k] + mdp[rt[i - 1]][k]);
			}
		}
		dbgr(ans[i], ans[i] + n + 1);
	}

	int q;
	cin >> q;
	while (q--)
	{
		int si;
		cin >> si;
		for (int i = n; i >= 0; i--)
		{
			if (ans[rt.size()][i] <= si)
			{
				cout << i << endl;
				break;
			}
		}
	}
	return 0;
}

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