Submission #487760

#	Time	Username	Problem	Language	Result	Execution time	Memory
487760		errorgorn	Kamenčići (COCI21_kamencici)	C++17	70 / 70	82 ms	175616 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

mt19937 rng(123123);

int n,k;
string s;

int tot=0;
int pref[355];

int memo[355][355][355];

int dp(int i,int j,int k){
	if (memo[i][j][k]!=-1) return memo[i][j][k];
	if (k==::k) return memo[i][j][k]=1;
	
	int other=tot-(pref[j]-pref[i-1])-k;
	int res=dp(i+1,j,other+(s[i]=='C'))&dp(i,j-1,other+(s[j]=='C'));
	
	res=1^res;
	
	//cerr<<i<<" "<<j<<" "<<k<<endl;
	return memo[i][j][k]=res;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	cin>>s;
	
	s="$"+s;
	
	rep(x,1,n+1){
		pref[x]=pref[x-1]+(s[x]=='C');
	}
	tot=pref[n];
	
	memset(memo,-1,sizeof(memo));
	
	if (dp(1,n,0)) cout<<"DA"<<endl;
	else cout<<"NE"<<endl;
}

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