Submission #658373

#	Time	Username	Problem	Language	Result	Execution time	Memory
658373		sam571128	Kamenčići (COCI21_kamencici)	C++17	70 / 70	55 ms	86696 KiB

Main

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

const int N = 355;
int dp[N][N][N], pref[N];

signed main(){
	fastio
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;

	int sum = 0;

	s = "$" + s;

	for(int i = 1; i <= n; i++){
		pref[i] = pref[i-1] + (s[i]=='C');
		sum += (s[i]=='C');
	}

	for(int l = n; l >= 1; l--){
		for(int r = l+1; r <= n; r++){
			for(int x = 0; x <= n; x++){
				int y = sum-(pref[r]-pref[l-1])-x;
				if(x >= k) dp[l][r][x] = false;
				else if(y >= k) dp[l][r][x] = true;
				else dp[l][r][x] = (!dp[l+1][r][y] || !dp[l][r-1][y]);
			}
		}
	}

	cout << (dp[1][n][0] ? "DA" : "NE") << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40