Submission #208145

#	Time	Username	Problem	Language	Result	Execution time	Memory
208145		dOAOb	Trobojnica (COCI19_trobojnica)	C++14	0 / 110	6 ms	504 KiB

trobojnica

#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 (!n && !cnct) return 1e12;
	
	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 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;
//	cout<<"##st: "<<st+1<<'\n';
	
	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;
	}
//	cout<<"##"; for (int x: ord) cout<<x+1<<' '; cout<<'\n';
//	exit(0);
	
	vector<int> ov(n);
	copy(v, v+n, ov.begin());
	
	for (int i=0;i<n;i++)
		v[i] = ov[ord[i]];
	
//	cout<<"#v: "; for (int i=0;i<n;i++) cout<<v[i]<<' '; cout<<'\n';
	
//	for (int j=0;j<=n;j++)
//		d(n-1, j, 0), d(n-1, j, 1);
	
	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));
	
//	cout<<"#"; for (int x: ans_len) cout<<x<<' '; cout<<'\n';
	
	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: 0 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50