oj.uz

Submission #862209

# Submission time Handle Problem Language Result Execution time Memory
862209 2023-10-17T17:23:06 Z Mizo_Compiler Kamenčići (COCI21_kamencici) C++14
70 / 70
 112 ms 337236 KB 
#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]-(k-rem) == k)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");
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 336980 KB Output is correct
2 Correct 112 ms 336856 KB Output is correct
3 Correct 104 ms 336812 KB Output is correct
4 Correct 94 ms 336980 KB Output is correct
5 Correct 90 ms 336920 KB Output is correct
6 Correct 89 ms 336852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 336980 KB Output is correct
2 Correct 112 ms 336856 KB Output is correct
3 Correct 104 ms 336812 KB Output is correct
4 Correct 94 ms 336980 KB Output is correct
5 Correct 90 ms 336920 KB Output is correct
6 Correct 89 ms 336852 KB Output is correct
7 Correct 88 ms 336968 KB Output is correct
8 Correct 88 ms 336980 KB Output is correct
9 Correct 92 ms 336776 KB Output is correct
10 Correct 89 ms 336960 KB Output is correct
11 Correct 88 ms 336980 KB Output is correct
12 Correct 88 ms 336888 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 336980 KB Output is correct
2 Correct 112 ms 336856 KB Output is correct
3 Correct 104 ms 336812 KB Output is correct
4 Correct 94 ms 336980 KB Output is correct
5 Correct 90 ms 336920 KB Output is correct
6 Correct 89 ms 336852 KB Output is correct
7 Correct 88 ms 336968 KB Output is correct
8 Correct 88 ms 336980 KB Output is correct
9 Correct 92 ms 336776 KB Output is correct
10 Correct 89 ms 336960 KB Output is correct
11 Correct 88 ms 336980 KB Output is correct
12 Correct 88 ms 336888 KB Output is correct
13 Correct 87 ms 336792 KB Output is correct
14 Correct 111 ms 337236 KB Output is correct
15 Correct 93 ms 336976 KB Output is correct
16 Correct 97 ms 336976 KB Output is correct
17 Correct 92 ms 337012 KB Output is correct
18 Correct 89 ms 336904 KB Output is correct