제출 #448818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
448818		Antekb	Džumbus (COCI19_dzumbus)	C++14	50 / 110	473 ms	8416 KiB

dzumbus

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const long long inf=1e18;
vector<long long> dp[2][N];//0-opt, 1-zawiera v
int siz[N], vis[N];
long long val[N];
vector<int> E[N];
void init(int v){
	vis[v]=1;
	for(int u:E[v]){
		if(!vis[u]){
			init(u);
		}
	}
}
void dfs(int v){
	siz[v]=1;
	dp[0][v]={0, inf};
	dp[1][v]={inf, inf};
	for(int u:E[v]){
		if(!siz[u]){
			dfs(u);
			siz[v]+=siz[u];
			vector<long long> V(siz[v]+1, inf), V2(siz[v]+1, inf);
			V[0]=0;
			for(int i=0; i<siz[v]-siz[u]; i++){
				for(int j=0; j<=siz[u]; j++){
					V[i+j]=min(V[i+j], dp[0][v][i]+min(dp[0][u][j], dp[1][u][j]));
					V2[i+j]=min(V2[i+j], dp[1][v][i]+min(dp[0][u][j], dp[1][u][j]));
				}
			}
			for(int i=0; i<siz[v]-siz[u]; i++){
				for(int j=0; j<=siz[u]; j++){
					V2[i+j+1]=min(V2[i+j+1], dp[0][v][i]+dp[1][u][j]+val[v]);
				}
			}
			for(int i=0; i<=siz[v]-siz[u]; i++){
				for(int j=0; j<siz[u]; j++){
					V2[i+j+1]=min(V2[i+j+1], dp[1][v][i]+dp[0][u][j]+val[u]);
				}
			}
			for(int i=0; i<siz[v]-siz[u]; i++){
				for(int j=0; j<siz[u]; j++){
					V2[i+j+2]=min(V2[i+j+2], dp[0][v][i]+dp[0][u][j]+val[v]+val[u]);
				}
			}
			for(int i=0; i<=siz[v]-siz[u]; i++){
				V[i]=min(V[i], dp[0][v][i]);
				V2[i]=min(V2[i], dp[1][v][i]);
			}
			dp[0][v]=V;
			dp[1][v]=V2;
		}
	}
	/*for(int i=siz[v]; i>=0; i--){
		dp[0][v][i]=min(dp[0][v][i], dp[1][v][i]);
		if(i!=siz[v]){
			dp[0][v][i]=min(dp[0][v][i], dp[0][v][i+1]);
		}
	}*/
}
int main(){
	int n, m;
	cin>>n>>m;
	val[0]=inf;
	for(int i=1; i<=n; i++)cin>>val[i];
	for(int i=0; i<m; i++){
		int u, v;
		cin>>u>>v;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			init(i);
			E[0].push_back(i);
		}
	}
	dfs(0);
	for(int i=siz[0]-1; i>=0; i--){
		dp[0][0][i]=min(dp[0][0][i], dp[0][0][i+1]);
	}
	//for(long long i:dp[0][0])cout<<i<<" ";cout<<"\n";
	int q;
	cin>>q;
	while(q--){
		int s;
		cin>>s;
		int t=upper_bound(dp[0][0].begin(), dp[0][0].end(), s)-dp[0][0].begin()-1;
		cout<<t<<"\n";
	}
}

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