oj.uz

Submission #537171

# Submission time Handle Problem Language Result Execution time Memory
537171 2022-03-14T17:15:16 Z davi_bart Kamenčići (COCI21_kamencici) C++14
0 / 70
 0 ms 340 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -