제출 #862207

#제출 시각아이디문제언어결과실행 시간메모리
862207Mizo_CompilerKamenčići (COCI21_kamencici)C++17
0 / 70
92 ms336980 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double ld; #define pb push_back #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define F first #define S second const int N = 350; int n, dp[N][N][N+1][2], k, p[N], s[N]; string st; int sol(int l, int r, int rem, bool t) { if (rem == 0)return 0; if (p[l]+s[r]-rem == 0)return 1; int &ret = dp[l][r][rem][t]; if (~ret)return ret; if (!t) { if (sol(l+1, r, rem - (!t && st[l]=='C'), !t) == 1)return ret = 1; if (sol(l, r-1, rem - (!t && st[r]=='C'), !t) == 1)return ret = 1; return ret = 0; } else { if (sol(l+1, r, rem - (!t && st[l]=='C'), !t) == 0)return ret = 0; if (sol(l, r-1, rem - (!t && st[r]=='C'), !t) == 0)return ret = 0; return ret = 1; } } int main () { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k >> st; p[0] = 0; for (int i = 1; i < n; i++) { p[i] = (p[i-1] + (st[i-1] == 'C')); } s[n-1] = 0; for (int i = n-2; i >= 0; i--) { s[i] = (s[i+1] + (st[i+1] == 'C')); } memset(dp, -1, sizeof dp); cout << (sol(0, n-1, k, 0) ? "DA" : "NE"); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...