Submission #641592

#	Time	Username	Problem	Language	Result	Execution time	Memory
641592		Chal1shkan	Kamenčići (COCI21_kamencici)	C++14	70 / 70	47 ms	50508 KiB

Main

# include <bits/stdc++.h>

# define mkp make_pair
# define ff first
# define ss second
# define pll pair <ll, ll>
# define pii pair <int, int>
 
# define vec vector
# define pb push_back
# define pf push_front
# define ppb pop_back
# define ppf pop_front

# define all(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
# define sz(x) ((int)(x).size())
# define lb lower_bound
# define ub upper_bound

# define br break
# define rt return 
# define cn continue
# define nl "\n"
# define off exit(0)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll MAXN = 1e5 + 25;
const ll MAXL = 18 + 0;
const ll INF1 = 1e18 + 0;
const ll INF2 = 2e9 + 0;
const ll MOD = 1e9 + 7;
const ll M0D = 998244353;
const ld PI = acos((ld) -1);
const ll P = 67 + 0 + 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

using namespace std;

void qataima ()
{
    ios::sync_with_stdio(false);
    
    cin.tie(0);
}

int n, k, pref[MAXN];
string s;
bool dp[405][405][405];
bool used[405][405][405];

bool search (int l, int r, int cnt, bool boo)
{
	if (l + r > n) rt 0;
	if (used[l][r][cnt]) rt dp[l][r][cnt];
	used[l][r][cnt] = 1;
	int sum = pref[l] + (pref[n] - pref[n - r]);
	if (sum - cnt == k) rt dp[l][r][cnt] = 1;
	if (cnt == k) rt dp[l][r][cnt] = 0;
	if (boo)
	{
		boo = 1 - boo;
		dp[l][r][cnt] = (search(l + 1, r, cnt + (s[l] == 'C'), boo) | search(l, r + 1, cnt + (s[n - 1 - r] == 'C'), boo));
	}
	else
	{
		boo = 1 - boo;
		dp[l][r][cnt] = (search(l + 1, r, cnt, boo) & search(l, r + 1, cnt, boo));
	}
	rt dp[l][r][cnt];
}

void ma1n ()
{
	cin >> n >> k;
	cin >> s;
	for (int i = 1; i <= n; ++i)
	{
		pref[i] = pref[i - 1] + (s[i - 1] == 'C');
	}
	int l = 0, r = 0, cnt = 0;
	bool boo = 1;
	cout << (search(l, r, cnt, boo) ? "DA" : "NE") << nl;
}
	
int main (/* <3 */)
{	
	qataima ();
	int zxc = 1;
//	cin >> zxc;
	while (zxc--)
	{
		ma1n();
	}
    return 0;
}

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