Submission #638565

#	Time	Username	Problem	Language	Result	Execution time	Memory
638565		NotLinux	Kamenčići (COCI21_kamencici)	C++14	70 / 70	175 ms	355412 KiB

Main

/**
 * author: NotLinux
 * created: 06.09.2022 ~ 09:33:06
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
    #include "/home/notlinux/debug.h"
#else
    #define debug(x...) void(37)
#endif
int n,k;string str;
vector<vector<vector<int>>>dp;
vector<int>pre,suff;
//state of a game is  1 if I won this state
//state of a game is  0 if I lost this state
int func(int l,int r,int z){
    if(l+r > n)return 0;
    if(dp[l][r][z]!=-1)return dp[l][r][z];//using dp optimization
 
    int toplam=pre[l]+suff[n-r];//number of the red pebbles in the range [0,l] + [r,n]
    //now we check if the game ends this turn
    if((toplam-z)==k){//has the opponent lost
        dp[l][r][z] = 1;
        return dp[l][r][z];//return that I won in this state
    }
    else if(z == k){//have I lost
        dp[l][r][z] = 0;
        return dp[l][r][z];//return that I lost in this state
    }
 
    //now we check what happens if we go from one of two cases : p1 and p2
    int p1,p2;//two possible cases
    if((l+r)%2==0){//is this my turn
        p1=func(l+1,r,z+(str[l]=='C'));//what happens if I take from left
        p2=func(l,r+1,z+(str[n-r-1]=='C'));//what happens if I take from right
    }
    else {//is this his turn
        p1=func(l+1,r,z);//what happens if he takes from left
        p2=func(l,r+1,z);//what happens if he takes from right
    }
 
 
    //if I won in p1 or p2 , than I won in this state , else I lost in this state , same logic for the opponent
    if((l+r)%2==0){//is this my turn
        dp[l][r][z] = p1|p2;//choose the optimal for urself
    }
    else {//is this his turn
        dp[l][r][z] = p1&p2;//he chooses optimal for himself
    }
 
 
    return dp[l][r][z];//return the state of the game
}
void solve(){
    cin>>n>>k>>str;
 
    dp.assign(n+5,vector<vector<int>>(n+5,vector<int>(n+5,-1)));
    pre.resize(n+1);suff.resize(n+1);
 
    for(int i=0;i<n;i++)pre[i+1]=pre[i]+(str[i]=='C');//building the prefix array
    for(int i=n;i>0;i--)suff[i-1]=suff[i]+(str[i-1]=='C');//building the suffix array
 
    cout<<(func(0,0,0)?"DA":"NE")<<endl;//if I won print DA
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    int tt=1;
    //cin >> tt;
    while(tt--)solve();
}

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