Submission #964433

#	Time	Username	Problem	Language	Result	Execution time	Memory
964433		AtabayRajabli	Kamenčići (COCI21_kamencici)	C++17	70 / 70	51 ms	126548 KiB

Main

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40