oj.uz

Submission #537193

# Submission time Handle Problem Language Result Execution time Memory
537193 2022-03-14T17:39:10 Z davi_bart Kamenčići (COCI21_kamencici) C++14
70 / 70
 46 ms 49708 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;
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Correct 1 ms 1872 KB Output is correct
14 Correct 46 ms 47444 KB Output is correct
15 Correct 11 ms 15816 KB Output is correct
16 Correct 32 ms 30100 KB Output is correct
17 Correct 40 ms 49708 KB Output is correct
18 Correct 14 ms 19976 KB Output is correct