Submission #926460

#	Time	Username	Problem	Language	Result	Execution time	Memory
926460		blackavar	Kamenčići (COCI21_kamencici)	C++14	70 / 70	218 ms	338752 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, f;
    cin >> n >> f;
    string s;
    cin >> s;
    s = ' ' + s;
    long long dp[n + 1][n + 1][n + 1];
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            for (int k = 0; k <= n; k++)
            {
                dp[i][j][k] = 0;
            }
        }
    }
    long long pref[n + 1];
    pref[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        pref[i] = pref[i - 1] + (s[i] == 'C');
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i >= j) continue;
            for (int k = 0; k <= n; k++)
            {
                long long other = pref[n] - (pref[j] - pref[i - 1]) - k;
                if (k >= f) dp[i][j][k] = 0;
                else if (other >= f) dp[i][j][k] = 1;
                else
                {
                    if (!dp[i + 1][j][other] || !dp[i][j - 1][other]) dp[i][j][k] = 1;
                    else dp[i][j][k] = 0;
                }
            }
        }
    }
    if (dp[1][n][0]) cout << "DA";
    else cout << "NE";
    return 0;
}

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