oj.uz

Submission #917424

# Submission time Handle Problem Language Result Execution time Memory
917424 2024-01-28T07:13:59 Z josanneo22 Kamenčići (COCI21_kamencici) C++17
70 / 70
 22 ms 43612 KB 
#include<bits/stdc++.h>
#include <random>
using namespace std;
namespace NEO {
	std::mt19937 cincai(std::chrono::steady_clock::now().time_since_epoch().count());
	using i64 = long long;
	#define L(i,j,k) for(int i=(j);i<=(k);++i)
	#define R(i,j,k) for(int i=(j);i>=(k);--i)
	#define all(x) x.begin(),x.end()
	#define me(x,a) memset(x,a,sizeof(x))
}using namespace NEO;

const int _ = 355;
int N, K, pre[_], total_red; 
string S;
bool dp[_][_][_];
/*
	dp[l][r][a] = can we win if we consider range [l,r] 
	dp[l][r] = !(dp[l + 1][r] || dp[l][r - 1])
*/
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> K >> S;
	S = ' ' + S;
	L(i, 1, N) pre[i] = pre[i - 1] + (S[i] == 'C'); 
	total_red = pre[N];
	R(l, N, 1) L(r, l + 1, N){
		L(have, 0, N){
			int other_person_have = total_red - (pre[r] - pre[l - 1]) - have;
			if(have >= K) dp[l][r][have] = false;
			else if(other_person_have >= K) dp[l][r][have] = true;
			else dp[l][r][have] = !(dp[l + 1][r][other_person_have] & dp[l][r - 1][other_person_have]);
		}
	}
	if(dp[1][N][0]) cout << "DA\n";
	else cout << "NE\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 0 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 0 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct
13 Correct 18 ms 43472 KB Output is correct
14 Correct 19 ms 43552 KB Output is correct
15 Correct 17 ms 41564 KB Output is correct
16 Correct 20 ms 43348 KB Output is correct
17 Correct 22 ms 43540 KB Output is correct
18 Correct 20 ms 43612 KB Output is correct