Submission #850170

#	Time	Username	Problem	Language	Result	Execution time	Memory
850170		Ne0n	Kamenčići (COCI21_kamencici)	C++14	0 / 70	46 ms	359560 KiB

Main

/*
                            -> Authored By : Ахмад <-
                              ->IM COMING BACKK<-
*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define F first
#define S second
#define endl '\n'
#define pb emplace_back
#define sqrt sqrtl
#define clr(A, Val) memset(A, Val, sizeof(A));
#define what_is(x) cerr << "->" << (#x) << " = " << x << endl
const int mod = 1e9 + 7, mod2 = 1e9 + 9, OO = 0x3f3f3f3f;
const long long lOO = 0x3f3f3f3f3f3f3f3f;
int add(ll a, ll b) { return (a + b) % mod; }
int mul(ll a, ll b) { return 1LL * a * b % mod; }
long long intlog(ll base, ll x) { return (log(x) / log(base)); }
long long Ceil(ll a, ll b) { return (a + b - 1) / b; }
template <typename T>
int32_t size_i(T &container) {
  return static_cast<int32_t>(container.size());
}
// MIST!?!?!?!?!?
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
//->  U Sure?!
template <typename T1, typename T2>
using safe_map = unordered_map<T1, T2, custom_hash>;

template <typename T>
istream &operator>>(istream &istream, vector<T> &v) {
  for (auto &it : v) cin >> it;
  return istream;
}
template <typename T>
ostream &operator<<(ostream &ostream, vector<T> &C) {
  for (auto &it : C) cout << it << " ";
  return ostream;
}
// Think again?!
void ________________________________() {
  int ____ = 0;
#ifndef ONLINE_JUDGE
  ____ = 1;
#endif
  if (____ == 0) {
    cin.tie(0)->sync_with_stdio(0);
  }
}
ll power(ll b, ll p) {
  if (p == 0) return 1;
  ll temp = power(b, p / 2);
  temp = temp * temp;
  if (p & 1) temp = temp * b;
  return temp;
}
//    OK?!
const int N = 3e5 + 1, BASE = 26, BASE2 = 37;
ll n, k;
string s;
ll pre[N]{}, dp[358][358][358];
ll get(ll st, ll ed) {
  if (st > ed) swap(st, ed);
  if (st < 0) return 0;
  if (ed >= n) return 0;
  if (st == 0) return pre[ed];
  return pre[ed] - pre[st - 1];
}
ll solve(ll l, ll r, ll a) {
  if (l > r) return 0;
  ll ans1 = get(0, l - 1) + get(r + 1, n - 1) - a;
  ans1 = max(ans1, 0ll);
  // cout << ans1 << " " << l << r << a << endl;
  if (ans1 > k) return 1;
  if (a > k) {
    return 0;
  }
  if (dp[l][r][a] != -1) return dp[l][r][a];
  ll op1 = 0, op2 = 0, op3 = 0, op4 = 0;  // we have 4 options
  op1 = solve(l + 2, r, a + (s[l] == 'C'));
  op2 = solve(l + 1, r - 1, a + (s[l] == 'C'));
  op3 = solve(l, r - 2, a + (s[r] == 'C'));
  op4 = solve(l + 1, r - 1, a + (s[r] == 'C'));
  return dp[l][r][a] = max({op1, op2, op3, op4});
}
void TestCases() {
  clr(dp, -1);
  cin >> n >> k >> s;
  pre[0] = (s[0] == 'C');
  for (ll i = 1; i < n; ++i) {
    pre[i] = pre[i - 1] + (s[i] == 'C');
  }
  // cout << get(n - 1, n - 1) << endl;
  ll o = (s[0] == 'C') + (s[n - 1] == 'C');
  bool V = solve(0, n - 1, o);
  if (V == 0)
    cout << "DA" << endl;
  else
    cout << "NE" << endl;
}

int main() {
  ________________________________();
  ll ____________ = 1;
  // cin >> ____________;
  cout << fixed << setprecision(12);
  while ((____________)--) {
    TestCases();
  }
  return 0;
}

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