제출 #208149

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

dzumbus

#include<iostream>
#include<algorithm>
#include<numeric>
#include<queue>
#include<tuple>
#include<map>
#include<set>
using namespace std;

#define int long long

#ifdef lioraju
	#define ndbg(x) 
#else
	#define ndbg(x) x
#endif

const int mxsz = 1e3 + 5;

int v[mxsz];
int dp[mxsz][mxsz][2];
bool vis[mxsz][mxsz][2];

vector<int> AE[mxsz];

int d(int n, int m, bool cnct)
{
	if (!m) return 0;
	if (n<0) return 1e12;
	if (vis[n][m][cnct]) return dp[n][m][cnct];
	
	vis[n][m][cnct] = 1;
	int mnn = d(n-1, m, 0);
	if (cnct) mnn = min(mnn, d(n-1, m-1, 1)+v[n]);
	if (n>=1) mnn = min(mnn, d(n-2, m-2, 1)+v[n]+v[n-1]);
	
	return dp[n][m][cnct] = mnn;
}

signed main()
{
	ndbg( ios::sync_with_stdio(0); cin.tie(0); );
	int n, m; cin>>n>>m;
	for (int i=0;i<n;i++)
		cin>>v[i];
	
	for (int i=0, a, b; i<m; i++)
		cin>>a>>b, --a, --b, AE[a].push_back(b), AE[b].push_back(a);
	
	int st = -1;
	for (int i=0;i<n;i++)
	{
		if (AE[i].size()<=1) st = i;
		if (AE[i].size()>2) return 1;
	}
	if (st==-1) return 1;
	
	vector<int> ord;
	{
		vector<bool> vis(n);
		
		vis[st] = 1, ord.push_back(st);
		
		int p = st;
		for (int i=1;i<n;i++)
			for (int x: AE[p])
				if (!vis[x]) vis[x] = 1, ord.push_back(x), p = x;
	}
	
	vector<int> ov(n);
	copy(v, v+n, ov.begin());
	
	for (int i=0;i<n;i++)
		v[i] = ov[ord[i]];
	
	vector<int> ans_len(n+1, 1e18);
	for (int i=0;i<n;i++)
		for (int j=0;j<=n;j++)
			ans_len[j] = min(ans_len[j], d(i, j, 0));
	
	int q; cin>>q;
	for (int qi=0; qi<q; qi++)
	{
		int S; cin>>S;
		int ans = 0;
		for (int j=n;j>=0;j--)
			if (ans_len[j] <= S) { ans = j; break; }
		
		cout<<ans<<'\n';
	}
}

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