Submission #205376

#	Time	Username	Problem	Language	Result	Execution time	Memory
205376		mraron	Džumbus (COCI19_dzumbus)	C++14	0 / 110	549 ms	26208 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];
	dp2[0][1][2]=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) {
				//cerr<<i<<" "<<j+k<<" "<<j<<" "<<k<<" "<<dp2[i-1][j][2]<<" lst "<<lst[i-1]<<", "<<min(dp2[i][j+k][2], dp2[i-1][j][2]+min(dp[lst[i-1]][k][1], dp[lst[i-1]][k][2]))<<"\n";
				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][0]=min(dp2[i][j+k][0], dp2[i-1][j+k][0]);
				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][1]=min(dp2[i][j+k][1], dp2[i-1][j+k][1]);
				dp2[i][j+k][2]=min(dp2[i][j+k][2], dp2[i-1][j][2]+min(dp[lst[i-1]][k][1], dp[lst[i-1]][k][2]));
				if(k>0) dp2[i][j+k][2]=min(dp2[i][j+k][2], min(dp2[i-1][j][0],min(dp2[i-1][j][2], dp2[i-1][j][1]))+min(dp[lst[i-1]][k][1], dp[lst[i-1]][k][2]));
				dp2[i][j+k][2]=min(dp2[i][j+k][2], dp2[i-1][j+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];
		}
	}
	dp[x][1][2]=1LL<<60;
	
	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";
	cerr<<dp[2][1][1]<<"\n";
	cerr<<dp[3][3][2]<<"\n";
	cerr<<dp[4][3][0]<<"\n";
	cerr<<s[1]<<"\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: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30