# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
717355 | 2023-04-01T21:27:03 Z | TheSahib | Kamenčići (COCI21_kamencici) | C++17 | 75 ms | 169568 KB |
#include <bits/stdc++.h> #define ll long long #define oo 1e9 #define pii pair<int, int> using namespace std; const int MAX = 351; int n, k; string s; int reds[MAX]; int dp[MAX][MAX][MAX]; bool f(int l, int r, int red){ if(dp[l][r][red] != -1) return dp[l][r][red]; if(red >= k) return 0; int red1 = reds[n] - (reds[r] - reds[l - 1]) - red; if(red1 >= k) return 1; if(l == r) return 0; if(f(l + 2, r, red + (s[l] == 'C')) && f(l + 1, r - 1, red + (s[l] == 'C'))) return dp[l][r][red] = 1; if(f(l, r - 2, red + (s[r] == 'C')) && f(l + 1, r - 1, red + (s[r] == 'C'))) return dp[l][r][red] = 1; return dp[l][r][red] = 0; } void solve(){ memset(dp, -1, sizeof(dp)); cin >> n >> k; cin >> s; s.insert(s.begin(), ' '); for (int i = 1; i <= n; i++) { reds[i] = reds[i - 1] + (s[i] == 'C'); } if(f(1, n, 0)){ cout << "DA\n"; } else{ cout << "NE\n"; } } int main() { solve(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 169468 KB | Output is correct |
2 | Correct | 62 ms | 169540 KB | Output is correct |
3 | Correct | 65 ms | 169460 KB | Output is correct |
4 | Correct | 74 ms | 169568 KB | Output is correct |
5 | Correct | 70 ms | 169480 KB | Output is correct |
6 | Correct | 68 ms | 169464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 169468 KB | Output is correct |
2 | Correct | 62 ms | 169540 KB | Output is correct |
3 | Correct | 65 ms | 169460 KB | Output is correct |
4 | Correct | 74 ms | 169568 KB | Output is correct |
5 | Correct | 70 ms | 169480 KB | Output is correct |
6 | Correct | 68 ms | 169464 KB | Output is correct |
7 | Correct | 71 ms | 169488 KB | Output is correct |
8 | Correct | 68 ms | 169420 KB | Output is correct |
9 | Correct | 75 ms | 169560 KB | Output is correct |
10 | Correct | 69 ms | 169420 KB | Output is correct |
11 | Correct | 64 ms | 169504 KB | Output is correct |
12 | Correct | 62 ms | 169512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 169468 KB | Output is correct |
2 | Correct | 62 ms | 169540 KB | Output is correct |
3 | Correct | 65 ms | 169460 KB | Output is correct |
4 | Correct | 74 ms | 169568 KB | Output is correct |
5 | Correct | 70 ms | 169480 KB | Output is correct |
6 | Correct | 68 ms | 169464 KB | Output is correct |
7 | Correct | 71 ms | 169488 KB | Output is correct |
8 | Correct | 68 ms | 169420 KB | Output is correct |
9 | Correct | 75 ms | 169560 KB | Output is correct |
10 | Correct | 69 ms | 169420 KB | Output is correct |
11 | Correct | 64 ms | 169504 KB | Output is correct |
12 | Correct | 62 ms | 169512 KB | Output is correct |
13 | Correct | 64 ms | 169460 KB | Output is correct |
14 | Correct | 67 ms | 169540 KB | Output is correct |
15 | Correct | 70 ms | 169564 KB | Output is correct |
16 | Correct | 66 ms | 169508 KB | Output is correct |
17 | Correct | 68 ms | 169444 KB | Output is correct |
18 | Correct | 67 ms | 169544 KB | Output is correct |