Submission #537171

#	Time	Username	Problem	Language	Result	Execution time	Memory
537171		davi_bart	Kamenčići (COCI21_kamencici)	C++14	0 / 70	0 ms	340 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N, K;
vector<int> v;
array<int, 2> memo[400][400];
bool vis[400][400];
array<int, 2> solve(int a, int b, bool turn) {
    if (a > b) return array<int, 2>{0, 0};
    if (vis[a][b]) return memo[a][b];
    vis[a][b] = 1;
    auto x = solve(a + 1, b, !turn);
    x[turn] += v[a];
    auto y = solve(a, b - 1, !turn);
    y[turn] += v[b];

    if (y[0] < x[0]) swap(x, y);
    if (turn) swap(x, y);

    if (x[1] >= K && x[0] < 1e8) x[1] = 1e9;
    if (x[0] >= K && x[1] < 1e8) x[0] = 1e9;
    return memo[a][b] = x;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N >> K;
    string x;
    cin >> x;
    for (char i : x) {
        v.pb(i == 'C');
    }

    if (solve(0, N - 1, 0)[0] < 1e8)
        cout << "DA\n";
    else
        cout << "NE\n";
}

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