Submission #1032714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032714		vjudge1	Kamenčići (COCI21_kamencici)	C++17	0 / 70	129 ms	172452 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 350, inf = 1e9;
int n, k;
string s;
vector<vector<vector<int> > > dp(N, vector<vector<int> > (N, vector<int> (N)));

int main()
{
  cin >> n >> k;
  cin >> s;

  for(int l = k - 1; l >= 0; l--)
    for(int i = n - 1; i >= 0; i--)
      {
	if(s[i] == 'P') dp[i][i][l] = 0;
	else if((n - 1) & 1) dp[i][i][l] = 1;
	else dp[i][i][l] = -inf;
	// cerr << "dp[" << i << "][" << i << "][" << l << "] = " << dp[i][i][l] << endl;	
	for(int j = i + 1; j < n; j ++)
	  {
	    if((n - (j - i + 1)) % 2 == 0) // if this is player 1 turn
	      {
		// cerr << i << ' ' << j << "I\n";
		dp[i][j][l] = -inf;
		if(s[i] == 'C' && l + 1 < k)
		  dp[i][j][l] = max(dp[i][j][l], dp[i + 1][j][l + 1]);
		else if(s[j] == 'P')
		  dp[i][j][l] = max(dp[i][j][l], dp[i + 1][j][l]);

		if(s[j] == 'C' && l + 1 < k)
		  dp[i][j][l] = max(dp[i][j][l], dp[i][j-1][l+1]);
		else if(s[j] == 'P')
		  dp[i][j][l] = max(dp[i][j][l], dp[i][j-1][l]);
	      }
	    else
	      {
		dp[i][j][l] = inf;
		if(s[i] == 'C')
		  dp[i][j][l] = min(dp[i][j][l], dp[i + 1][j][l] + 1);
		else
		  dp[i][j][l] = min(dp[i][j][l], dp[i + 1][j][l]);

		if(s[j] == 'C')
		  dp[i][j][l] = min(dp[i][j][l], dp[i][j-1][l] + 1);
		else
		  dp[i][j][l] = min(dp[i][j][l], dp[i][j-1][l]);
	      }

	    // cerr << "dp[" << i << "][" << j << "][" << l << "] = " << dp[i][j][l] << endl;
	  }
      }
  // cerr << dp[0][n-1][0] << endl;
  bool ans = (dp[0][n - 1][0] >= k);
  cout << (ans ? "DA" : "NE") << endl;
  return 0;
}

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