oj.uz

Submission #964433

# Submission time Handle Problem Language Result Execution time Memory
964433 2024-04-16T20:20:12 Z AtabayRajabli Kamenčići (COCI21_kamencici) C++17
70 / 70
 51 ms 126548 KB 
#include <bits/stdc++.h>

// author : a1abay

#define all(v)      v.begin(), v.end()
#define GCD(a, b)   __gcd(a, b)
#define LCM(a, b)   (a*b / (__gcd(a, b)))

typedef long long           ll;
const int inf =             1e9 + 7;
const int inff =            (int)1e18 + 7;
const int sz =              351;
using namespace             std;

int n, k;
string s;
bool dp[sz][sz][sz][2], used[sz][sz][sz][2];
int p[sz];

// dp[l][r][cnt][0 / 1] = if the current player is going to win if they start in the range [l, r] with cnt reds so far

int f(int l, int r, int cnt, int t)
{
    if(l > r)return 0;
    if(used[l][r][cnt][t])return dp[l][r][cnt][t];
    used[l][r][cnt][t] = 1;
    dp[l][r][cnt][t] = 0;
    if(cnt + (s[l] == 'C') < k)dp[l][r][cnt][t] |= !f(l + 1, r, p[n] - p[r] + p[l] - cnt - (s[l] == 'C'), t ^ 1);
    if(cnt + (s[r] == 'C') < k)dp[l][r][cnt][t] |= !f(l, r - 1, p[n] - p[r - 1] + p[l - 1] - cnt - (s[r] == 'C'), t ^ 1);
    return dp[l][r][cnt][t];
}

signed main()   
{       
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k >> s;
    s = ' ' + s;
    for(int i = 1; i <= n; i++)p[i] = p[i - 1] + (s[i] == 'C');
    cout << (f(1, n, 0, 0) ? "DA" : "NE") << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2516 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2516 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 2 ms 9048 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 8864 KB Output is correct
12 Correct 3 ms 13404 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2516 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 2 ms 9048 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 8864 KB Output is correct
12 Correct 3 ms 13404 KB Output is correct
13 Correct 3 ms 15960 KB Output is correct
14 Correct 51 ms 124756 KB Output is correct
15 Correct 18 ms 58712 KB Output is correct
16 Correct 36 ms 93524 KB Output is correct
17 Correct 39 ms 126548 KB Output is correct
18 Correct 16 ms 70236 KB Output is correct