oj.uz

Submission #626694

# Submission time Handle Problem Language Result Execution time Memory
626694 2022-08-11T16:16:20 Z vovamr Kamenčići (COCI21_kamencici) C++17
70 / 70
 63 ms 85840 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline void solve() {
	int n, k;
	cin >> n >> k;
	string s; cin >> s;

	ve<int> a(n + 2);
	for (int i = 1; i <= n; ++i) a[i] = (s[i - 1] == 'C' ? 1 : 0);

	ve<int> pf(n + 2);
	for (int i = 1; i <= n; ++i) pf[i] = pf[i - 1] + a[i];
	pf[n + 1] = pf[n];

	ve<ve<ve<int>>> dp(n+2,ve<ve<int>>(n+2,ve<int>(k+1,-1)));

	function<int(int, int, int)> dfs = [&](int l, int r, int taken) {
		if (~dp[l][r][taken]) return dp[l][r][taken];

		int sum = pf[l] + pf[n + 1] - (!r ? 0 : pf[r - 1]) - taken;
		int moves = l + n + 1 - r;

		if (taken == k) return (dp[l][r][taken] = 1);

		dp[l][r][taken] = 0;
		dp[l][r][taken] |= !dfs(l + 1, r, sum + a[l + 1]);
		dp[l][r][taken] |= !dfs(l, r - 1, sum + a[r - 1]);

		return dp[l][r][taken];
	};
	int val = dfs(0, n + 1, 0);
	cout << (val ? "DA" : "NE");
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:41:7: warning: unused variable 'moves' [-Wunused-variable]
   41 |   int moves = l + n + 1 - r;
      |       ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 0 ms 460 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 488 KB Output is correct
12 Correct 1 ms 596 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 0 ms 460 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 488 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 12 ms 18764 KB Output is correct
14 Correct 56 ms 24520 KB Output is correct
15 Correct 15 ms 13396 KB Output is correct
16 Correct 63 ms 54732 KB Output is correct
17 Correct 58 ms 85840 KB Output is correct
18 Correct 38 ms 54748 KB Output is correct