답안 #579049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579049	2022-06-18T10:51:49 Z	Trisanu_Das	Kamenčići (COCI21_kamencici)	C++17	70 / 70	84 ms	169596 KB

Main

#include <bits/stdc++.h>
using namespace std;
#define N 351
 
int n, k; string s;
 
int dp[351][351][351], red[351];
 
void memo(int l, int r, int m){
  if(dp[l][r][m] != -1) return;
  int already_coll = 0;
  if(l != 0) already_coll = red[n - 1] - m - red[r] + red[l - 1];
  else already_coll = red[n - 1] - m - red[r];
  if(m >= k){
    dp[l][r][m] = 0; return;
  }
  if(already_coll >= k){
    dp[l][r][m] = 1; return;
  }
  if(l == r){
	dp[l][r][m] = 0; return;
  }
  memo(l + 1, r, already_coll); memo(l, r - 1, already_coll);
  dp[l][r][m] = (!dp[l + 1][r][already_coll] || !dp[l][r - 1][already_coll]);
}
 
int main(){
    cin >> n >> k >> s;
	red[0] = (s[0] == 'C');
	memset(dp, -1, sizeof(dp));
	for(int i = 1; i < n; i++) red[i] = red[i - 1] + (s[i] == 'C');
	memo(0, n - 1, 0);
	if(dp[0][n - 1][0]) cout << "DA\n";
	else cout << "NE\n";
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	169420 KB	Output is correct
2	Correct	64 ms	169492 KB	Output is correct
3	Correct	66 ms	169460 KB	Output is correct
4	Correct	63 ms	169548 KB	Output is correct
5	Correct	62 ms	169444 KB	Output is correct
6	Correct	62 ms	169596 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	169420 KB	Output is correct
2	Correct	64 ms	169492 KB	Output is correct
3	Correct	66 ms	169460 KB	Output is correct
4	Correct	63 ms	169548 KB	Output is correct
5	Correct	62 ms	169444 KB	Output is correct
6	Correct	62 ms	169596 KB	Output is correct
7	Correct	62 ms	169468 KB	Output is correct
8	Correct	63 ms	169452 KB	Output is correct
9	Correct	64 ms	169472 KB	Output is correct
10	Correct	62 ms	169504 KB	Output is correct
11	Correct	63 ms	169528 KB	Output is correct
12	Correct	61 ms	169548 KB	Output is correct

Subtask #3

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	169420 KB	Output is correct
2	Correct	64 ms	169492 KB	Output is correct
3	Correct	66 ms	169460 KB	Output is correct
4	Correct	63 ms	169548 KB	Output is correct
5	Correct	62 ms	169444 KB	Output is correct
6	Correct	62 ms	169596 KB	Output is correct
7	Correct	62 ms	169468 KB	Output is correct
8	Correct	63 ms	169452 KB	Output is correct
9	Correct	64 ms	169472 KB	Output is correct
10	Correct	62 ms	169504 KB	Output is correct
11	Correct	63 ms	169528 KB	Output is correct
12	Correct	61 ms	169548 KB	Output is correct
13	Correct	64 ms	169536 KB	Output is correct
14	Correct	84 ms	169544 KB	Output is correct
15	Correct	65 ms	169480 KB	Output is correct
16	Correct	81 ms	169560 KB	Output is correct
17	Correct	70 ms	169548 KB	Output is correct
18	Correct	64 ms	169484 KB	Output is correct