oj.uz

Submission #641592

# Submission time Handle Problem Language Result Execution time Memory
641592 2022-09-17T06:04:35 Z Chal1shkan Kamenčići (COCI21_kamencici) C++14
70 / 70
 47 ms 50508 KB 
# 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 476 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 476 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 628 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 476 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 628 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Correct 2 ms 1868 KB Output is correct
14 Correct 47 ms 48500 KB Output is correct
15 Correct 12 ms 16216 KB Output is correct
16 Correct 34 ms 30816 KB Output is correct
17 Correct 44 ms 50508 KB Output is correct
18 Correct 17 ms 20424 KB Output is correct