Submission #1276888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276888		SmuggingSpun	Džumbus (COCI19_dzumbus)	C++20	0 / 110	122 ms	1096 KiB

dzumbus

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
typedef long long ll;
const int lim = 1e3 + 5;
const ll INF = 1e18;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
int n, m, cnt[lim];
ll D[lim];
vector<int>g[lim];
bitset<lim>vis;
vector<vector<ll>>dfs(int s, int p = -1){
	cnt[s] = 1;
	vis[s] = true;
	vector<vector<ll>>dp(2, vector<ll>(2, INF));
	dp[0][0] = 0;
	for(int& d : g[s]){
		if(d != p){
			vector<vector<ll>>f = dfs(d, s);
			cnt[s] += cnt[d];
			while(dp.size() <= cnt[s]){
				dp.push_back(vector<ll>(2, INF));
			}
			for(int i = cnt[s]; i > 0; i--){
				for(int j = min(i, cnt[d]); j > 0; j--){
					minimize(dp[i][0], dp[i - j][0] + min(f[j][0], f[j][1]));
					minimize(dp[i][1], dp[i - j][1] + min(f[j][0], f[j][1]));
					if(i > j){
						minimize(dp[i][1], dp[i - j - 1][0] + f[j][1] + D[s]);
					}
				}
				minimize(dp[i][1], dp[i - 1][1] + D[d]);
				if(i > 1){
					minimize(dp[i][1], dp[i - 2][0] + D[d] + D[s]);
				}
			}
		}
	}
	return dp;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> D[i];
	}
	for(int i = 0; i < m; i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vis.reset();
	vector<ll>dp(n + 1, INF);
	dp[0] = 0;
	for(int i = 1; i <= n; i++){
		if(!vis[i]){
			vector<vector<ll>>f = dfs(i);
			for(int j = n; j > 0; j--){
				for(int k = min(cnt[i], j); k > 0; k--){
					minimize(dp[j], dp[j - k] + min(f[k][0], f[k][1]));
				}
			}
		}
	}
	int q;
	cin >> q;
	for(int _ = dp[1] = 0; _ < q; _++){
		ll x;
		cin >> x;
		cout << (n == 1 || x < dp[2] ? 0 : upper_bound(dp.begin(), dp.end(), x) - dp.begin() - 1) << "\n";
	}
}

Compilation message (stderr)

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:48:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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