oj.uz

Submission #579049

# Submission time Handle Problem Language Result Execution time Memory
579049 2022-06-18T10:51:49 Z Trisanu_Das Kamenčići (COCI21_kamencici) C++17
70 / 70
 84 ms 169596 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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