Submission #537184

#	Time	Username	Problem	Language	Result	Execution time	Memory
537184		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[turn] >= K) {
        x[turn] = 1e9;
        x[!turn] = -1e9;
    }
    // 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);
    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] < 1e8)
        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:44: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]
   44 |     assert(v.size() == N);
      |            ~~~~~~~~~^~~~

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