Submission #338203

#	Time	Username	Problem	Language	Result	Execution time	Memory
338203		minoum	Džumbus (COCI19_dzumbus)	C++17	20 / 110	77 ms	42220 KiB

dzumbus

#include<bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
 
const int MAXN = 1000+10;
const ll inf = 1e17;
int n, q, m;
ll dp[MAXN][MAXN][3], s[MAXN][MAXN], d[MAXN], sz[MAXN], d2[MAXN][3], mn[MAXN][MAXN], ans[MAXN];
vector <int> adj[MAXN], rs;
bool mark[MAXN];
 
void dfs(int v){
	mark[v] = true; sz[v] = 1;
	dp[v][0][0] = 0ll; dp[v][0][1] = d[v]; mn[v][0] = 0ll;
	for(int u: adj[v]){
		if(mark[u]) continue;
		dfs(u);
		for(int i = 0; i <= sz[u]+sz[v]; i++){
			d2[i][0] = dp[v][i][0];
			d2[i][1] = dp[v][i][1];
			d2[i][2] = dp[v][i][2];
			
			//d2[i][0] = d2[i][1] = d2[i][2] = inf;
		}
		for(int i = 0; i <= sz[v]; i++)
			for(int j = i; j <= sz[u]+sz[v]; j++){
				d2[j][0] = min(d2[j][0], dp[v][i][0]+mn[u][j-i]);
				d2[j][1] = min(d2[j][1], dp[v][i][1]+dp[u][j-i][0]);
				d2[j][2] = min(d2[j][2], dp[v][i][2]+min(dp[u][j-i][0], dp[u][j-i][2]));
				if(j-i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i][1]+dp[u][j-i-1][2]);
				if(i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i-1][1]+dp[u][j-i][2]);
				if(j-i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i][2]+dp[u][j-i-1][1]);
				if(i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i-1][2]+dp[u][j-i][1]);
				if(j-i-2>=0) d2[j][2] = min(d2[j][2], dp[v][i][1]+dp[u][j-i-2][1]);
				if(i-2>=0) d2[j][2] = min(d2[j][2], dp[v][i-2][1]+dp[u][j-i][1]);
				if(i-1>=0 && j-i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i-1][1]+dp[u][j-i-1][1]);
			}
		for(int i = 0; i <= sz[u]+sz[v]; i++){
			dp[v][i][0] = min(inf, d2[i][0]);
			dp[v][i][1] = min(inf, d2[i][1]);
			dp[v][i][2] = min(inf, d2[i][2]);
		}
		sz[v] += sz[u];
	}
	for(int i = 0; i <= sz[v]; i++)
		mn[v][i] = min(dp[v][i][0], min(dp[v][i][1], dp[v][i][2]));
	return;
}
 
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> d[i]; 
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= n; j++) dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = mn[i][j] = inf;
	for(int i = 0; i < m; i++){
		int u, v;
		cin	>> u >> v; u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 0; i <= n; i++)
		for(int j = 1; j <= n; j++) s[i][j] = inf;
	int cnt = 0;
	for(int v = 0; v < n; v++)
		if(!mark[v]){
			dfs(v);
			rs.push_back(v); cnt++;
			int ss = ((rs.empty())?0:sz[rs.back()]);
			for(int i = 0; i <= ss; i++)
				for(int j = 0; j <= sz[v]; j++)
					s[cnt][i+j] = min(s[cnt][i+j], s[cnt-1][i]+mn[v][j]);
			/*cout << "v:" << v+1 << '\n';
			for(int i = 0; i <= sz[v]; i++) cout << mn[v][i] << " ";
			cout << '\n';*/
		}
	ans[n] = s[cnt][n];
	for(int i = n-1; i >=0; i--) ans[i] = min(ans[i+1], s[cnt][i]);
	
	cin >> q;
	while(q--){
		ll qs;
		cin >> qs;
		int ind = upper_bound(ans, ans+n, qs) - ans - 1;
		cout << ind << '\n';
	}
/*	cout << "ans?" << endl;
	for(int i = 0; i <= n; i++) cout << ans[i] << " ";
	cout << endl;*/
	return 0; 
}

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