Submission #698636

#	Time	Username	Problem	Language	Result	Execution time	Memory
698636		ld_minh4354	Kamenčići (COCI21_kamencici)	C++14	70 / 70	253 ms	515188 KiB

Main

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

#define fi first
#define se second
#define pb push_back

int n,k,dpsave[355][355][355][3],a[355],lc[355],rc[355];

int dp(int l,int r,int c,int t)
{
	if (dpsave[l][r][c][t]!=-1) return dpsave[l][r][c][t];
	if (c>=k)
	{
		dpsave[l][r][c][t]=0;
//		cout<<l<<" "<<r<<" "<<c<<" "<<t<<" "<<"0a"<<"\n";
		return 0;
	}
	if (lc[l]+rc[r]-c>=k)
	{
		dpsave[l][r][c][t]=1;
//		cout<<l<<" "<<r<<" "<<c<<" "<<t<<" "<<"1a"<<"\n";
		return 1;
	}
	
	int ans;
	if (t==0) ans=max(dp(l+1, r, c + a[l+1], 1-t), dp(l, r+1, c + a[n-r], 1-t));
	else 	  ans=min(dp(l+1, r, c         , 1-t), dp(l, r+1, c         , 1-t));
	
	dpsave[l][r][c][t]=ans;
//	cout<<l<<" "<<r<<" "<<c<<" "<<t<<" "<<ans<<"\n";
	return ans;
}

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	string s;
	int i,j,w;
	
	cin>>n>>k>>s;
	for (i=1;i<n+1;i++) if (s[i-1]=='C') a[i]=1;else a[i]=0;
	
	lc[0]=0;
	for (i=1;i<n+1;i++) lc[i]=lc[i-1]+a[i];
	
	rc[0]=0;
	for (i=1;i<n+1;i++) rc[i]=rc[i-1]+a[n+1-i];
	
	for (i=0;i<n+1;i++) for (j=0;j<n+1;j++) for (w=0;w<n+1;w++) dpsave[i][j][w][0]=dpsave[i][j][w][1]=-1;
	
	if (dp(0,0,0,0)==1) cout<<"DA";else cout<<"NE";
//	cout<<dpsave[0][0][0][0];
}

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