Submission #917424

#	Time	Username	Problem	Language	Result	Execution time	Memory
917424		josanneo22	Kamenčići (COCI21_kamencici)	C++17	70 / 70	22 ms	43612 KiB

Main

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40