oj.uz

Submission #981953

# Submission time Handle Problem Language Result Execution time Memory
981953 2024-05-13T17:07:29 Z samek08 Kamenčići (COCI21_kamencici) C++14
0 / 70
 1 ms 6492 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()

const int MAXN = 355, INF = 2e9+50;
const ull INF_L = (ull)1e19+500;

int n,k;
string A;
bool dp[MAXN][MAXN][MAXN];
bool dp2[MAXN][MAXN][MAXN];

void solve()
{
	cin >> n >> k >> A;

	rep(i,n)
	{
		if(A[i] == 'P')
		{
			dp2[i][i][1] = 1;	
		}
	}
	for(int len = 2; len <= n; ++len)
	{
		for(int j = 0; j+len-1 < n; ++j)
		{
			int l = j, p = j+len-1;
			for(int c = 1; c <= k; ++c)
			{
				dp[l][p][c] = 0;
				dp2[l][p][c] = 0;

				if(c == 1)
				{
					if(A[l] == 'P' and !dp[l+1][p][c]) dp[l][p][c] = 1;
					if(A[p] == 'P' and !dp[l][p-1][c]) dp[l][p][c] = 1;

					if(A[l] == 'P' and !dp2[l+1][p][c]) dp2[l][p][c] = 1;
					if(A[p] == 'P' and !dp2[l][p-1][c]) dp2[l][p][c] = 1;
				}
				else
				{
					if(A[l] == 'C' and !dp2[l+1][p][c]) dp[l][p][c] = 1;
					if(A[l] == 'P' and !dp[l+1][p][c]) dp[l][p][c] = 1;

					if(A[p] == 'C' and !dp2[l][p-1][c]) dp[l][p][c] = 1;
					if(A[p] == 'P' and !dp[l][p-1][c]) dp[l][p][c] = 1;

					if(A[l] == 'C' and !dp[l+1][p][c-1]) dp2[l][p][c] = 1;
					if(A[l] == 'P' and !dp2[l+1][p][c]) dp2[l][p][c] = 1;

					if(A[p] == 'C' and !dp[l][p-1][c-1]) dp2[l][p][c] = 1;
					if(A[p] == 'P' and !dp2[l][p-1][c]) dp2[l][p][c] = 1;
				}
				//cout << "L: " << l << " P: " << p << " C: " << c << " VAL: " << dp[l][p][c] << endl;
			}
		}
	}

	if(dp[0][n-1][k] == 1) cout << "DA" << '\n';
	else cout << "NE" << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); 

    int T = 1;
   	//cin >> T;
    while(T--) solve();

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -