Submission #1263351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263351		gry3125	Kamenčići (COCI21_kamencici)	C++20	70 / 70	93 ms	175432 KiB

Main

#include <bits/stdc++.h>
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
typedef long long int ll;
using namespace std;

int n, k; string s;
vector<int> pre;
int m[355][355][355];

bool dp(int L, int R, int a) {
	if (a >= k) return m[L][R][a] = 0;
	if (pre[n]-pre[R]+pre[L-1]-a >= k) return m[L][R][a] = 1;
	if (L >= R) return m[L][R][a] = 0;
	if (m[L][R][a] != -1) return m[L][R][a];
	bool ok = (s[L] == 'C');
	bool p1 = dp(L+2, R, a+ok);
	bool p2 = dp(L+1, R-1, a+ok);
	ok = (s[R] == 'C');
	bool p3 = dp(L+1, R-1, a+ok);
	bool p4 = dp(L, R-2, a+ok);
	return m[L][R][a] = ((p1 && p2) || (p3 && p4));
}

int main() {
    owo
    cin >> n >> k >> s; s = '.'+s;
    pre.resize(n+1);
    for (int i = 1; i <= n; i++) {
    	pre[i] = pre[i-1];
    	if (s[i] == 'C') pre[i]++;
    }
    for (int i = 0; i < 355; i++) {
    	for (int j = 0; j < 355; j++) {
    		for (int l = 0; l < 355; l++) {
    			m[i][j][l] = -1;
    		}
    	}
    }
    bool ans = dp(1, n, 0);
    cout << (ans ? "DA" : "NE");
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40