Submission #537193

#	Time	Username	Problem	Language	Result	Execution time	Memory
537193		davi_bart	Kamenčići (COCI21_kamencici)	C++14	70 / 70	46 ms	49708 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;
bool memo[400][400][400];
bool vis[400][400][400];
bool solve(int a, int b, int cur, int tot) {
    bool turn = (N - (b - a + 1)) % 2;
    // if (a > b) return cur<K && ;
    if (cur >= K) return turn;
    if (tot - cur >= K) return !turn;

    if (vis[a][b][cur]) return memo[a][b][cur];
    vis[a][b][cur] = 1;
    int k = tot + v[a];
    bool x = solve(a + 1, b, tot - cur, k);
    k = tot + v[b];
    bool y = solve(a, b - 1, tot - cur, k);

    if (!turn) return memo[a][b][cur] = max(x, y);
    return memo[a][b][cur] = min(x, y);
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K;
    string x;
    cin >> x;
    for (char i : x) {
        v.pb(i == 'C');
    }
    assert(v.size() == N);

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

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:2:
Main.cpp: In function 'int main()':
Main.cpp:40:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   40 |     assert(v.size() == N);
      |            ~~~~~~~~~^~~~

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