Submission #703979

#	Time	Username	Problem	Language	Result	Execution time	Memory
703979		KazmetreD	Kamenčići (COCI21_kamencici)	C++17	70 / 70	146 ms	242972 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "debug.h"
#else
#define debug(x) void(37)
#endif

#define lsb(x) ((x)&(-x))
#define all(x) x.begin(),x.end()
#define setprec(n) cout << fixed << showpoint;cout << setprecision(n);
typedef long long ll;
typedef long double ld;
const ld eps = 1e-10;
const ll MOD1 = 1e9+7;
const ll MOD2 = 998244353;
const ll LINF = 1e18;
const int IINF = 1e9;
#define int ll

const int maxn = 355;
int n, k;
string str;
int dp[maxn][maxn][maxn];
int cm[maxn][maxn][maxn];
vector<int> pref, suff;

int go(int l, int r, int tk){
    int turn = (n-(r-l)) % 2;
    if(turn){ // branka's turn
        int br = (suff[r] + pref[l]) - tk;
        if(br >= k) return 0;
        if(tk >= k) return 1;

        int can = 0;
        if(str[l] == 'C' && br + 1 < k) can |= !go(l+1, r, tk);
        else if(str[l] != 'C') can |= !go(l+1, r, tk);

        if(str[r-1] == 'C' && br + 1 < k) can |= !go(l, r-1, tk);
        else if(str[r-1] != 'C') can |= !go(l, r-1, tk);
    
        return can;
    }
    else{ // anton's turn
        if(tk >= k) return 0;
        if((suff[r] + pref[l]) - tk >= k) return 1;
        if(cm[l][r][tk]) return dp[l][r][tk];

        int can = 0;
        if(str[l] == 'C' && tk + 1 < k) can |= !go(l+1, r, tk+1);
        else if(str[l] != 'C') can |= !go(l+1, r, tk);

        if(str[r-1] == 'C' && tk + 1 < k) can |= !go(l, r-1, tk+1);
        else if(str[r-1] != 'C') can |= !go(l, r-1, tk);
    
        cm[l][r][tk] = 1;
        return dp[l][r][tk] = can;
    }
}

void solve(){
    cin >> n >> k;
    cin >> str;

    pref.resize(n+1), suff.resize(n+1);
    for(int i = 1;i <= n;i++) pref[i] = pref[i-1] + (str[i-1] == 'C');
    for(int i = n-1;i >= 0;i--) suff[i] = suff[i+1] + (str[i] == 'C');

    if(go(0, n, 0)) cout << "DA" << "\n";
    else cout << "NE" << "\n";
}


signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    mt19937 mt(time(NULL));
    //setprec(10);

    //freopen("sleepy.in", "r", stdin);
    //freopen("in.txt", "w", stdout);

    int t = 1;
    //cin >> t;
    for(int i = 1;i <= t;i++)
        solve();

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40