oj.uz

Submission #529887

# Submission time Handle Problem Language Result Execution time Memory
529887 2022-02-23T23:54:45 Z penguinhacker Kamenčići (COCI21_kamencici) C++14
70 / 70
 71 ms 168128 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 168004 KB Output is correct
2 Correct 59 ms 168008 KB Output is correct
3 Correct 62 ms 168064 KB Output is correct
4 Correct 63 ms 168088 KB Output is correct
5 Correct 64 ms 168080 KB Output is correct
6 Correct 58 ms 168068 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 168004 KB Output is correct
2 Correct 59 ms 168008 KB Output is correct
3 Correct 62 ms 168064 KB Output is correct
4 Correct 63 ms 168088 KB Output is correct
5 Correct 64 ms 168080 KB Output is correct
6 Correct 58 ms 168068 KB Output is correct
7 Correct 62 ms 168044 KB Output is correct
8 Correct 62 ms 168088 KB Output is correct
9 Correct 69 ms 167988 KB Output is correct
10 Correct 62 ms 167988 KB Output is correct
11 Correct 64 ms 168060 KB Output is correct
12 Correct 58 ms 168004 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 168004 KB Output is correct
2 Correct 59 ms 168008 KB Output is correct
3 Correct 62 ms 168064 KB Output is correct
4 Correct 63 ms 168088 KB Output is correct
5 Correct 64 ms 168080 KB Output is correct
6 Correct 58 ms 168068 KB Output is correct
7 Correct 62 ms 168044 KB Output is correct
8 Correct 62 ms 168088 KB Output is correct
9 Correct 69 ms 167988 KB Output is correct
10 Correct 62 ms 167988 KB Output is correct
11 Correct 64 ms 168060 KB Output is correct
12 Correct 58 ms 168004 KB Output is correct
13 Correct 59 ms 168096 KB Output is correct
14 Correct 71 ms 168128 KB Output is correct
15 Correct 62 ms 168004 KB Output is correct
16 Correct 68 ms 168044 KB Output is correct
17 Correct 64 ms 168092 KB Output is correct
18 Correct 62 ms 168036 KB Output is correct