Submission #1181103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181103		Fikrat_Asadzadeh	Kamenčići (COCI21_kamencici)	C++20	70 / 70	82 ms	180548 KiB

Main

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

#define ll int
#define FORI(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, n) for(ll i = 1; i <= n; i++)
typedef vector < ll > vl; 
typedef set < ll > setl;
#define ff first
#define ss second    
#define all(v) v.begin(), v.end() 
#define pll pair<ll, ll> 
#define db double
#define nll cout << "\n"
#define nl "\n"
#define sync ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll poww(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1)res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
const ll mod =  998244353;
const int sz = 350 + 23 ;
const long long imax = LLONG_MAX;
ll n, m, k, res, q, x, y;
ll a[sz];
string s;
ll dp[sz][sz][sz], pref[sz];
ll f(ll l, ll r, ll c){
    if(~dp[l][r][c])return dp[l][r][c];
    ll c2 = pref[n] - pref[r] + pref[l - 1] - c;
    if(c >= k)return dp[l][r][c] = 0;
    else if(c2 >= k)return dp[l][r][c] = 1;
    else{
        ll x1 = f(l + 1, r, c2), x2 = f(l, r - 1, c2);
        if(!x1 || !x2)return dp[l][r][c] = 1;
        else return dp[l][r][c] = 0;
    }

}   
void solve(){
    cin >> n >> k;
    FOR(i, n){
        FOR(j, n){
            FORI(c, n + 1)dp[i][j][c] = -1;
        }
    }
    cin >> s;
    s = ' ' + s;
    FOR(i, n){
        pref[i] += pref[i - 1] + (s[i] == 'C');
    }
    ll x = f(1, n, 0);
    cout << (x ? "DA" : "NE");
}   
//IOI rice hub
signed main(){      
    // freopen("input.txt","r",stdin);a
    // freopen("output.txt","w",stdout);
    sync;
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }   
}

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