Submission #205645

#	Time	Username	Problem	Language	Result	Execution time	Memory
205645		mraron	Džumbus (COCI19_dzumbus)	C++14	110 / 110	794 ms	34296 KiB

dzumbus

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> adj[1111];
int b0[1111];
ll s[1111];
void dfs0(int x){
	b0[x]=1;
	for(auto i:adj[x]) {
		if(!b0[i]) dfs0(i);
	}
}

//0 -> not choosen
//1 -> choosen alone
//2 -> choosen with group
ll dp[1002][1002][3];
int b1[1111];
int sz[1111];
int dfs1(int x) {
	b1[x]=1;
	vector<int> lst;
	sz[x]=1;
	for(auto i:adj[x]) {
		if(!b1[i]) {
			sz[x]+=dfs1(i);
			lst.push_back(i);
		}
	}
	
	if(lst.empty()) {
		dp[x][1][1]=s[x];
		dp[x][0][0]=0;
		return sz[x];
	}
	ll dp2[lst.size()+1][sz[x]+1][3];
	memset(dp2, 0x0F, sizeof dp2);
	dp2[0][0][0]=0;
	dp2[0][1][1]=s[x];
	int eddig=1;
	for(int i=1;i<(int)lst.size()+1;++i) {
		for(int j=0;j<=eddig;++j) {
			for(int k=0;k<=sz[lst[i-1]];++k) {
				for(int l=0;l<3;++l) 
					dp2[i][j+k][l]=min(dp2[i][j+k][l], dp2[i-1][j+k][l]);
				dp2[i][j+k][0]=min(dp2[i][j+k][0], dp2[i-1][j][0]+min(dp[lst[i-1]][k][0], dp[lst[i-1]][k][2]));
				dp2[i][j+k][1]=min(dp2[i][j+k][1], dp2[i-1][j][1]+dp[lst[i-1]][k][0]);
				dp2[i][j+k][2]=min(dp2[i][j+k][2], dp2[i-1][j][2]+dp[lst[i-1]][k][0]);
				dp2[i][j+k][2]=min(dp2[i][j+k][2], min(dp2[i-1][j][2], dp2[i-1][j][1])+min(dp[lst[i-1]][k][1], dp[lst[i-1]][k][2]));
				
			}
		}
		eddig+=sz[lst[i-1]];
	}
	for(int i=0;i<=eddig;++i) {
		for(int j=0;j<3;++j) {
			dp[x][i][j]=dp2[lst.size()][i][j];
		}
	}
	
	return sz[x];
}


int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>s[i];
	for(int i=0;i<m;++i) {
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	int root=n+1;
	for(int i=1;i<=n;++i) {
		if(!b0[i]) {
			adj[root].push_back(i);
			adj[i].push_back(root);
			dfs0(i);
		}
	}
	memset(dp,0x0F,sizeof dp);
	dfs1(root);
	int q;
	cin>>q;
	//cerr<<dp[1][8][2]<<"\n";
	
	while(q--) {
		int x;
		cin>>x;
		int ans=0;
		for(int i=0;i<=n;++i) {
			if(dp[root][i][0]<=x) {
				ans=max(ans, i);
			}
		}
		cout<<ans<<"\n";
	}
}

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