oj.uz

답안 #1032778

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032778 2024-07-24T08:26:57 Z vjudge1 Kamenčići (COCI21_kamencici) C++17
0 / 70
 1 ms 856 KB 
#include<bits/stdc++.h>

using namespace std;

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

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

  int pref[n + 1] = {};
  for(int i = 0; i < n; i ++)
    pref[i + 1] = pref[i] + s[i] == 'C';

  int tot = pref[n];
  for(int i = n - 1; i >= 0; i --)
    {
      if(tot - (s[i] == 'C') >= 2 * k - 1)
	dp[i][i] = (n & 1) ? -inf : 0;
      else
	{
	  if((n - 1) & 1)
	    dp[i][i] = 1;
	  else
	    dp[i][i] = -inf;
	}
      // cerr << i << ' ' << i  << ' ' << dp[i][i] << endl;
      for(int j = i + 1; j < n; j ++)
	{
	  if(pref[i] + pref[j + 1] >= 2 * k + 1)
	    dp[i][j] = ((n - j + i - 1) % 2 == 0) ? -inf : 0;
	  else
	    {
	      bool turn = (n - (j - i + 1)) & 1;
	      if(turn) // this is second player turn
		dp[i][j] = min(dp[i + 1][j] + (s[i] == 'C'), dp[i][j - 1] + (s[j] == 'C'));
	      else
		dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
	    }
	  // cout << i << ' ' << j << ' '  << dp[i][j] << endl;
	}
    }
  // cerr << dp[0][n -1] << endl;
  if(dp[0][n - 1] >= k)
    cout << "DA" << endl;
  else
    cout << "NE" << endl;
  return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -