#include<iostream>
#include<string>
using namespace std;
int n,k;
int dp[351][351][351];
string kam;
int Czy_zn_C(int t)
{
return kam[t]=='C';
}
int wejdz(int l, int p, int ilemaB)
{
if(dp[l][p][ilemaB]!=0)
return dp[l][p][ilemaB];
if(ilemaB==0)
{
dp[l][p][ilemaB]=1;
return dp[l][p][ilemaB];
}
if(l==p)
{
if(n%2==0)
{
dp[l][p][ilemaB]=1;
}
else
{
if(kam[l]=='C')
dp[l][p][ilemaB]=2;
else
dp[l][p][ilemaB]=1;
}
}
else
{
dp[l][p][ilemaB]=10000;
if((n-(p-l+1))%2==0)
{
//Ruch A
dp[l][p][ilemaB]=min(wejdz(l+1,p,ilemaB)+Czy_zn_C(l),
wejdz(l,p-1,ilemaB)+Czy_zn_C(p));
}
else
{
//Ruch B
dp[l][p][ilemaB]=max(wejdz(l+1,p,ilemaB-Czy_zn_C(l)),
wejdz(l,p-1,ilemaB-Czy_zn_C(p)));
}
}
return dp[l][p][ilemaB];
}
int main()
{
cin>>n>>k;
cin>>kam;
if(wejdz(0,n-1,k)>k)
printf("NE");
else
printf("DA");
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
564 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
560 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
564 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
560 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
696 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
2 ms |
2132 KB |
Output is correct |
10 |
Correct |
2 ms |
1748 KB |
Output is correct |
11 |
Correct |
1 ms |
1620 KB |
Output is correct |
12 |
Correct |
1 ms |
2004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
564 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
560 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
696 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
2 ms |
2132 KB |
Output is correct |
10 |
Correct |
2 ms |
1748 KB |
Output is correct |
11 |
Correct |
1 ms |
1620 KB |
Output is correct |
12 |
Correct |
1 ms |
2004 KB |
Output is correct |
13 |
Correct |
2 ms |
2516 KB |
Output is correct |
14 |
Correct |
93 ms |
85156 KB |
Output is correct |
15 |
Correct |
62 ms |
75552 KB |
Output is correct |
16 |
Correct |
89 ms |
82008 KB |
Output is correct |
17 |
Correct |
57 ms |
84856 KB |
Output is correct |
18 |
Correct |
23 ms |
35844 KB |
Output is correct |