Submission #529887

#	Time	Username	Problem	Language	Result	Execution time	Memory
529887		penguinhacker	Kamenčići (COCI21_kamencici)	C++14	70 / 70	71 ms	168128 KiB

Main

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

#define ll long long
#define ar array

const int mxN=350;
int n, k, dp[mxN][mxN][mxN], p[mxN+1];
string s;

bool solve(int i, int j, int a) {
	//cout << i << " " << j << " " << a << endl;
	if (dp[i][j][a]!=-1)
		return dp[i][j][a];
	if (a==k)
		return dp[i][j][a]=0;
	if (p[n]-p[j+1]+p[i]-a==k) {
		//cout << "WIN " << i << " " << j << " " << a << endl;
		return dp[i][j][a]=1;
	}
	if ((n-(j-i+1))%2==0) // first player
		return dp[i][j][a]=solve(i+1, j, a+(s[i]=='C'))||solve(i, j-1, a+(s[j]=='C'));
	return dp[i][j][a]=solve(i+1, j, a)&&solve(i, j-1, a);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k >> s;
	for (int i=0; i<n; ++i)
		p[i+1]=p[i]+(s[i]=='C');
	memset(dp, -1, sizeof(dp));
	cout << (solve(0, n-1, 0)?"DA":"NE");
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'bool solve(int, int, int)':
Main.cpp:16:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   16 |   return dp[i][j][a]=0;
      |          ~~~~~~~~~~~^~
Main.cpp:19:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   19 |   return dp[i][j][a]=1;
      |          ~~~~~~~~~~~^~
Main.cpp:22:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   22 |   return dp[i][j][a]=solve(i+1, j, a+(s[i]=='C'))||solve(i, j-1, a+(s[j]=='C'));
      |          ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   23 |  return dp[i][j][a]=solve(i+1, j, a)&&solve(i, j-1, a);
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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