oj.uz

Submission #548100

# Submission time Handle Problem Language Result Execution time Memory
548100 2022-04-12T12:21:12 Z aryan12 Kamenčići (COCI21_kamencici) C++17
70 / 70
 153 ms 338840 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, k;
string s;
const int N = 351;
int dp[N][N][N];
int pref[N];

void recur(int l, int r, int num_pebbles)
{
	if(dp[l][r][num_pebbles] != -1)
	{
		return;
	}
	int opp_pebbles = 0;
	if(l != 0) opp_pebbles = pref[n - 1] - num_pebbles - pref[r] + pref[l - 1];
	else opp_pebbles = pref[n - 1] - num_pebbles - pref[r];
	if(num_pebbles >= k)
	{
		dp[l][r][num_pebbles] = 0;
		return;
	}
	if(opp_pebbles >= k)
	{
		dp[l][r][num_pebbles] = 1;
		return;
	}
	if(l == r)
	{
		dp[l][r][num_pebbles] = 0;
		return;
	}
	recur(l + 1, r, opp_pebbles);
	recur(l, r - 1, opp_pebbles);
	if(dp[l + 1][r][opp_pebbles] == 0 || dp[l][r - 1][opp_pebbles] == 0)
	{
		dp[l][r][num_pebbles] = 1;
		return;
	}
	dp[l][r][num_pebbles] = 0;
	return;
}

void Solve() 
{
	cin >> n >> k >> s;
	pref[0] = (s[0] == 'C');
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			for(int l = 0; l < N; l++)
			{
				dp[i][j][l] = -1;
			}
		}
	}
	for(int i = 1; i < n; i++)
	{
		pref[i] = pref[i - 1] + (s[i] == 'C');
	}
	recur(0, n - 1, 0);
	if(dp[0][n - 1][0] == 1)
	{
		cout << "DA\n";
	}
	else
	{
		cout << "NE\n";
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 338688 KB Output is correct
2 Correct 126 ms 338816 KB Output is correct
3 Correct 124 ms 338760 KB Output is correct
4 Correct 134 ms 338780 KB Output is correct
5 Correct 137 ms 338724 KB Output is correct
6 Correct 148 ms 338776 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 338688 KB Output is correct
2 Correct 126 ms 338816 KB Output is correct
3 Correct 124 ms 338760 KB Output is correct
4 Correct 134 ms 338780 KB Output is correct
5 Correct 137 ms 338724 KB Output is correct
6 Correct 148 ms 338776 KB Output is correct
7 Correct 131 ms 338840 KB Output is correct
8 Correct 143 ms 338748 KB Output is correct
9 Correct 135 ms 338792 KB Output is correct
10 Correct 127 ms 338756 KB Output is correct
11 Correct 127 ms 338772 KB Output is correct
12 Correct 127 ms 338752 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 338688 KB Output is correct
2 Correct 126 ms 338816 KB Output is correct
3 Correct 124 ms 338760 KB Output is correct
4 Correct 134 ms 338780 KB Output is correct
5 Correct 137 ms 338724 KB Output is correct
6 Correct 148 ms 338776 KB Output is correct
7 Correct 131 ms 338840 KB Output is correct
8 Correct 143 ms 338748 KB Output is correct
9 Correct 135 ms 338792 KB Output is correct
10 Correct 127 ms 338756 KB Output is correct
11 Correct 127 ms 338772 KB Output is correct
12 Correct 127 ms 338752 KB Output is correct
13 Correct 145 ms 338756 KB Output is correct
14 Correct 148 ms 338832 KB Output is correct
15 Correct 131 ms 338824 KB Output is correct
16 Correct 153 ms 338792 KB Output is correct
17 Correct 137 ms 338716 KB Output is correct
18 Correct 136 ms 338800 KB Output is correct