oj.uz

답안 #1032714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032714 2024-07-24T06:43:40 Z vjudge1 Kamenčići (COCI21_kamencici) C++17
0 / 70
 129 ms 172452 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 172452 KB Output is correct
2 Incorrect 129 ms 172372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 172452 KB Output is correct
2 Incorrect 129 ms 172372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 172452 KB Output is correct
2 Incorrect 129 ms 172372 KB Output isn't correct
3 Halted 0 ms 0 KB -