Submission #861736

#	Time	Username	Problem	Language	Result	Execution time	Memory
861736		Cyber_Wolf	Kamenčići (COCI21_kamencici)	C++17	70 / 70	109 ms	501364 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lg long long 

const lg N = 400;

lg dp[N][N][N], pref[N];
lg n, k;
string s;

lg solve(lg l, lg r, lg o)
{
	if(o >= k)	return 0;
	if(pref[l-1]+pref[n]-pref[r]-o >= k)	return 1;
	auto&ret = dp[l][r][o];
	if(~ret)	return ret;
	if((l-1+n-r)%2)
	{
		ret = min(solve(l+1, r, o), solve(l, r-1, o));
	}
	else{
		ret = max(solve(l+1, r, o+(s[l-1] == 'C')), solve(l, r-1, o+(s[r-1] == 'C')));
	}
	// cout << l << ' ' << r << ' ' << o << '\n';
	// cout << ret << '\n';
	return ret;
}

int main()
{
	cin >> n >> k;
	cin >> s;
	for(int i = 1; i <= n; i++)
	{
		pref[i] = pref[i-1]+(s[i-1] == 'C');
	}
	memset(dp, -1, sizeof(dp));
	cout << (solve(1, n, 0) ? "DA" : "NE") << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40