oj.uz

Submission #926459

# Submission time Handle Problem Language Result Execution time Memory
926459 2024-02-13T04:16:18 Z blackavar Kamenčići (COCI21_kamencici) C++14
0 / 70
 0 ms 600 KB 
#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 <= pref[j] - pref[i - 1]; 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -