Submission #981953

#	Time	Username	Problem	Language	Result	Execution time	Memory
981953		samek08	Kamenčići (COCI21_kamencici)	C++14	0 / 70	1 ms	6492 KiB

Main

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40