oj.uz

Submission #702131

# Submission time Handle Problem Language Result Execution time Memory
702131 2023-02-23T04:42:44 Z shmad Kamenčići (COCI21_kamencici) C++17
70 / 70
 238 ms 501380 KB 
#pragma GCC optimize("O3", "unroll-loops") // "Ofast" 	
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

const int N = 1e6 + 5, mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const ld eps = 1e-6;

int n, k, dp[400][400][400], p[N];
string s;

bool rec (int l, int r, int f) {
	int s = p[n] - (p[r] - p[l - 1]) - f;
	int &res = dp[l][r][f];
	if (res != -1) return res;
	if (f >= k) res = 0;
	if (s >= k) res = 1;
	if (res != -1) return res;
	res = (!rec(l + 1, r, s) || !rec(l, r - 1, s));
	return res;
}

void solve () {
	cin >> n >> k >> s;
	s = ' ' + s;
	for (int i = 1; i <= n; i++) p[i] = p[i - 1] + (s[i] == 'C');
	memset(dp, -1, sizeof(dp));
	cout << (rec(1, n, 0) ? "DA" : "NE");
	cout << '\n';
}

bool testcases = 0;

signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	cin.tie(0) -> sync_with_stdio(0);
	int test = 1;
	if (testcases) cin >> test;
	for (int cs = 1; cs <= test; cs++) {
		solve();
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 501180 KB Output is correct
2 Correct 185 ms 501284 KB Output is correct
3 Correct 192 ms 501196 KB Output is correct
4 Correct 184 ms 501256 KB Output is correct
5 Correct 210 ms 501252 KB Output is correct
6 Correct 182 ms 501192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 501180 KB Output is correct
2 Correct 185 ms 501284 KB Output is correct
3 Correct 192 ms 501196 KB Output is correct
4 Correct 184 ms 501256 KB Output is correct
5 Correct 210 ms 501252 KB Output is correct
6 Correct 182 ms 501192 KB Output is correct
7 Correct 195 ms 501380 KB Output is correct
8 Correct 180 ms 501280 KB Output is correct
9 Correct 183 ms 501224 KB Output is correct
10 Correct 186 ms 501208 KB Output is correct
11 Correct 191 ms 501176 KB Output is correct
12 Correct 209 ms 501168 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 501180 KB Output is correct
2 Correct 185 ms 501284 KB Output is correct
3 Correct 192 ms 501196 KB Output is correct
4 Correct 184 ms 501256 KB Output is correct
5 Correct 210 ms 501252 KB Output is correct
6 Correct 182 ms 501192 KB Output is correct
7 Correct 195 ms 501380 KB Output is correct
8 Correct 180 ms 501280 KB Output is correct
9 Correct 183 ms 501224 KB Output is correct
10 Correct 186 ms 501208 KB Output is correct
11 Correct 191 ms 501176 KB Output is correct
12 Correct 209 ms 501168 KB Output is correct
13 Correct 186 ms 501172 KB Output is correct
14 Correct 195 ms 501300 KB Output is correct
15 Correct 238 ms 501220 KB Output is correct
16 Correct 198 ms 501264 KB Output is correct
17 Correct 189 ms 501216 KB Output is correct
18 Correct 181 ms 501292 KB Output is correct