Submission #1272026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272026		sweetwibu2k8	Džumbus (COCI19_dzumbus)	C++20	0 / 110	27 ms	16944 KiB

dzumbus

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

#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define p_q priority_queue
#define bit(n, i) (((n)>>(i))&1)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;

const int M = 1e3 + 6;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;

int d[M], n, sz[M];
vector <int> g[M];
bool visited[M];
ll dp[M][M][2], lmao[M];

void dfs (int u, int parent)
{
	dp[u][0][0] = 0; dp[u][1][1] = d[u];
	sz[u] = 1;
	visited[u] = true;
	for (int v : g[u])
	{
		if (v == parent) continue;
		dfs (v, u);

		for (int k = sz[u]; k >= 0; k --)
		{
			for (int j = 0; j <= sz[v]; j ++)
			{
				dp[u][j + k][0] = min ({dp[u][j + k][0], dp[v][j][0] + dp[u][k][0]});
				dp[u][j + k][1] = min ({dp[u][j + k][1], dp[u][k][0] + dp[v][j][1], dp[u][k][1] + dp[v][j][0], dp[u][k][1] + dp[v][j][1]});
			}
		}
		sz[u] += sz[v];
	}

	for (int k = n; k >= 1; k --)
	{
		dp[u][k][1] = min (dp[u][k - 1][1] + d[u], dp[u][k - 1][0] + d[u]);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen (".inp", "r", stdin);
//	freopen (".out", "w", stdout);

	int m; cin >> n >> m;
	for (int i = 1; i <= n; i ++) cin >> d[i];
	for (int i = 1; i <= m; i ++)
	{
		int u, v; cin >> u >> v;
		g[u].pb (v);
		g[v].pb (u);
	}

	memset (dp, 0x3f, sizeof dp);
	memset (lmao, 0x3f, sizeof lmao);
	lmao[0] = 0;
	for (int i = 1; i <= n; i ++) if (!visited[i])
	{
		dfs (i, 0);
		for (int j = n; j >= 0; j --)
			for (int k = 0; k + j <= n; k ++)
				lmao[j + k] = min ({lmao[j + k], lmao[j] + dp[i][k][1], lmao[j] + dp[i][k][0]});
	}

	int q; cin >> q;
	while (q --)
	{
		ll x; cin >> x;
		int id = upper_bound (lmao + 1, lmao + n + 1, x) - lmao - 1;
		if (id == 1) id = 0;
		cout << id << endl;
	}
	return 0;
}

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