oj.uz

Submission #208177

# Submission time Handle Problem Language Result Execution time Memory
208177 2020-03-10T07:17:01 Z dOAOb Džumbus (COCI19_dzumbus) C++14
50 / 110
 198 ms 21000 KB 
#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 col)
{
	if (m<=0 && !col) return 0;
	if (n<0) return 1e12;
	if (vis[n][m][col]) return dp[n][m][col];
	
	vis[n][m][col] = 1;
//	int mnn = d(n-1, m, 0);
	int mnn = 1e12;
	if (col)
	{
		if (n)
		{
			mnn = min(d(n-1, m-1, 1)+v[n], d(n-1, m-1, 0)+v[n]+v[n-1]);
		}
	}
	else mnn = min(d(n-1, m-1, 1), 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][col] = 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));
			if (j) ans_len[j] = min(ans_len[j], d(i, j-1, 1));
		}
	
//	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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 18168 KB Output is correct
2 Correct 54 ms 18296 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 18168 KB Output is correct
2 Correct 54 ms 18296 KB Output is correct
3 Correct 102 ms 20344 KB Output is correct
4 Correct 112 ms 21000 KB Output is correct
5 Correct 198 ms 20728 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 376 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 18168 KB Output is correct
2 Correct 54 ms 18296 KB Output is correct
3 Correct 102 ms 20344 KB Output is correct
4 Correct 112 ms 21000 KB Output is correct
5 Correct 198 ms 20728 KB Output is correct
6 Runtime error 5 ms 376 KB Execution failed because the return code was nonzero
7 Halted 0 ms 0 KB -