제출 #862260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862260		AbdelmagedNour	Kamenčići (COCI21_kamencici)	C++17	70 / 70	42 ms	175696 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int N=355;
int n,k,dp[N][N][N],pre[N];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dp, -1, sizeof dp);
	cin>>n>>k;
	string str;
	cin>>str;
	str=str;
	for(int i=1;i<=n;i++)pre[i]=pre[i-1]+(str[i-1]=='C');
	for(int l=n;l>=1;l--){
		for(int r=l;r<=n;r++){
			for(int cnt=0;cnt<=n;cnt++){
				if(cnt>=k){
					dp[l][r][cnt]=0;
					continue;
				}
				int cnt2=pre[n]-cnt-(pre[r]-pre[l-1]);
				if(cnt2>=k)dp[l][r][cnt]=1;
				else dp[l][r][cnt]=(!dp[l+1][r][cnt2])||(!dp[l][r-1][cnt2]);
			}
		}
	}
	cout<<(dp[1][n][0]?"DA\n":"NE\n");
	return 0;
}

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