제출 #1266257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266257		canhnam357	Kamenčići (COCI21_kamencici)	C++20	70 / 70	89 ms	168776 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define N 350
int dp[N][N][N], g[N][N];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp, -1, sizeof dp);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int f = 0;
        for (int j = n - 1; j >= i; j--) {
            g[i][j] = f + sum;
            f += (s[j] == 'C');
        }
        sum += (s[i] == 'C');
    }
    function<int(int, int, int)> solve = [&](int fi, int l, int r) {
        if (l > r) return 1;
        // cout << fi << ' ' << l << ' ' << r << '\n';
        // if (fi < 0 || fi > k) exit(0);
        if (dp[fi][l][r] != -1) return dp[fi][l][r];
        int ans = 1;
        if (fi > 1) {
            if (s[l] == 'C') ans &= solve(2 * k - g[l][r] - fi, l + 1, r);
            else ans &= solve(2 * k - g[l][r] - fi, l + 1, r);
            if (s[r] == 'C') ans &= solve(2 * k - g[l][r] - fi, l, r - 1);
            else ans &= solve(2 * k - g[l][r] - fi, l, r - 1);
        }
        else {
            if (s[l] == 'C' && s[r] == 'C') return dp[fi][l][r] = 0;
            if (s[l] == 'P') ans &= solve(2 * k - g[l][r] - fi, l + 1, r);
            if (s[r] == 'P') ans &= solve(2 * k - g[l][r] - fi, l, r - 1);
        }
        return dp[fi][l][r] = 1 - ans;
    };
    cout << (solve(k, 0, n - 1) ? "DA" : "NE") << '\n';
    return 0;
}

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