답안 #861736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861736	2023-10-16T21:19:10 Z	Cyber_Wolf	Kamenčići (COCI21_kamencici)	C++17	70 / 70	109 ms	501364 KB

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	105 ms	501228 KB	Output is correct
2	Correct	97 ms	501156 KB	Output is correct
3	Correct	103 ms	501316 KB	Output is correct
4	Correct	92 ms	501332 KB	Output is correct
5	Correct	92 ms	501332 KB	Output is correct
6	Correct	91 ms	501300 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	105 ms	501228 KB	Output is correct
2	Correct	97 ms	501156 KB	Output is correct
3	Correct	103 ms	501316 KB	Output is correct
4	Correct	92 ms	501332 KB	Output is correct
5	Correct	92 ms	501332 KB	Output is correct
6	Correct	91 ms	501300 KB	Output is correct
7	Correct	92 ms	501328 KB	Output is correct
8	Correct	90 ms	501180 KB	Output is correct
9	Correct	90 ms	501332 KB	Output is correct
10	Correct	89 ms	501168 KB	Output is correct
11	Correct	91 ms	501196 KB	Output is correct
12	Correct	93 ms	501252 KB	Output is correct

Subtask #3

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	105 ms	501228 KB	Output is correct
2	Correct	97 ms	501156 KB	Output is correct
3	Correct	103 ms	501316 KB	Output is correct
4	Correct	92 ms	501332 KB	Output is correct
5	Correct	92 ms	501332 KB	Output is correct
6	Correct	91 ms	501300 KB	Output is correct
7	Correct	92 ms	501328 KB	Output is correct
8	Correct	90 ms	501180 KB	Output is correct
9	Correct	90 ms	501332 KB	Output is correct
10	Correct	89 ms	501168 KB	Output is correct
11	Correct	91 ms	501196 KB	Output is correct
12	Correct	93 ms	501252 KB	Output is correct
13	Correct	91 ms	501332 KB	Output is correct
14	Correct	109 ms	501180 KB	Output is correct
15	Correct	93 ms	501188 KB	Output is correct
16	Correct	105 ms	501328 KB	Output is correct
17	Correct	98 ms	501364 KB	Output is correct
18	Correct	91 ms	501328 KB	Output is correct