Submission #1265526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265526		namhh	Kamenčići (COCI21_kamencici)	C++20	70 / 70	52 ms	86852 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 355;
int n,k,a[N],dp[N][N][N];
string s;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k >> s;
	s = "#"+s;
	for(int len = 1; len <= n; len++){
		for(int l = 1; l+len-1 <= n; l++){
			int r = l+len-1;
			int lim = 0;
			for(int i = 1; i < l; i++) lim += (s[i] == 'C');
			for(int i = r+1; i <= n; i++) lim += (s[i] == 'C');
			for(int i = 0; i <= lim; i++){
				int rem = lim-i;
				if(rem >= k) dp[l][r][i] = 1;
				else if(i < k && rem < k) dp[l][r][i] = 1-min(dp[l+1][r][rem],dp[l][r-1][rem]);
			}
		}
	}
	if(dp[1][n][0] == 1) cout << "DA";
	else cout << "NE";
}

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