답안 #658373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658373	2022-11-13T03:36:57 Z	sam571128	Kamenčići (COCI21_kamencici)	C++17	70 / 70	55 ms	86696 KB

Main

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

const int N = 355;
int dp[N][N][N], pref[N];

signed main(){
	fastio
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;

	int sum = 0;

	s = "$" + s;

	for(int i = 1; i <= n; i++){
		pref[i] = pref[i-1] + (s[i]=='C');
		sum += (s[i]=='C');
	}

	for(int l = n; l >= 1; l--){
		for(int r = l+1; r <= n; r++){
			for(int x = 0; x <= n; x++){
				int y = sum-(pref[r]-pref[l-1])-x;
				if(x >= k) dp[l][r][x] = false;
				else if(y >= k) dp[l][r][x] = true;
				else dp[l][r][x] = (!dp[l+1][r][y] || !dp[l][r-1][y]);
			}
		}
	}

	cout << (dp[1][n][0] ? "DA" : "NE") << "\n";
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	584 KB	Output is correct
6	Correct	1 ms	580 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	584 KB	Output is correct
6	Correct	1 ms	580 KB	Output is correct
7	Correct	2 ms	2132 KB	Output is correct
8	Correct	1 ms	1860 KB	Output is correct
9	Correct	1 ms	2132 KB	Output is correct
10	Correct	1 ms	1876 KB	Output is correct
11	Correct	1 ms	1876 KB	Output is correct
12	Correct	1 ms	2004 KB	Output is correct

Subtask #3

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	1 ms	584 KB	Output is correct
6	Correct	1 ms	580 KB	Output is correct
7	Correct	2 ms	2132 KB	Output is correct
8	Correct	1 ms	1860 KB	Output is correct
9	Correct	1 ms	2132 KB	Output is correct
10	Correct	1 ms	1876 KB	Output is correct
11	Correct	1 ms	1876 KB	Output is correct
12	Correct	1 ms	2004 KB	Output is correct
13	Correct	46 ms	86696 KB	Output is correct
14	Correct	51 ms	86168 KB	Output is correct
15	Correct	38 ms	78108 KB	Output is correct
16	Correct	45 ms	85148 KB	Output is correct
17	Correct	55 ms	85692 KB	Output is correct
18	Correct	45 ms	85196 KB	Output is correct