Submission #861742

#TimeUsernameProblemLanguageResultExecution timeMemory
861742HossamHero7Kamenčići (COCI21_kamencici)C++14
0 / 70
154 ms355412 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' int n,k; string s; int dp[355][355][355]; vector<int> prefix, suffix; int solve(int l,int r,int cnt){ bool turn = (l + n-r-1)&1; int rem = prefix[l] + suffix[r+1] - cnt; if(l>r) return rem == k ? !turn : 0; if(cnt==k) return (turn); if(rem == k) return !turn; int &ret = dp[l][r][cnt]; if(~ret) return ret; bool c1 = solve(l+1,r,cnt+(s[l]=='C'&&!turn)); bool c2 = solve(l,r-1,cnt+(s[r]=='C'&&!turn)); return ret = !(c1&c2); } void solve(){ cin>>n>>k; cin>>s; prefix.resize(n), suffix.resize(n+1); for(int i=1;i<=n;i++) prefix[i] = (s[i-1] == 'C') + prefix[i-1]; for(int i=n-1;i>=0;i--) suffix[i] = (s[i] == 'C') + suffix[i+1]; memset(dp,-1,sizeof(dp)); cout<<(solve(0,n-1,0)?"DA":"NE")<<endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...