Submission #494315

#	Time	Username	Problem	Language	Result	Execution time	Memory
494315		ktkerem	Kamenčići (COCI21_kamencici)	C++17	70 / 70	250 ms	341812 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll _i=0;
#define ffn(x) _i=x
#define llll pair<ll , ll>
#define stitr set<llll>::iterator
#define fora(y,x) for(ll y=_i;x>y;y++)
#define pb push_back
#define pf push_front
#define debu cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e13 + 7; 
const ll ous=1e6 + 5;
const ll dx[4] = {1 , -1 , 0 , 0} , dy[4] = {0,0,-1,1};
ll dp[352][352][352] , pref[352] , n , k;
string h;
ll fun(ll l , ll r , ll ot){
    ll &res = dp[l][r][ot];
    if(res == -1){
        ll tr = pref[n-1] , rl = pref[r];
        if(l > 0){
            rl-= pref[l-1];
        }
        ll ots =tr - rl - ot;
        if(ot >= k){
            res = 0;
        }
        else if(ots >= k){
            res = 1;
        }
        else{
            if(!fun(l+1 , r , ots) || !fun(l , r-1 , ots)){
                res = 1;
            }
            else{
                res = 0;
            }
        }
    }
    return res;
}
void solve(){
    memset(dp , -1 , sizeof(dp));
    cin >> n >> k >> h;
    pref[0] = (h[0] == 'C');
    for(ll i=1;n>i;i++){
        pref[i] = pref[i-1] + (h[i]=='C'); 
    }
    if(fun(0 , n-1 , 0)){
        cout << "DA\n";
    }
    else{
        cout << "NE\n";
    }
    return;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll t=1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0; 
}

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