oj.uz

Submission #866733

# Submission time Handle Problem Language Result Execution time Memory
866733 2023-10-27T01:05:36 Z becaido Kamenčići (COCI21_kamencici) C++17
70 / 70
 28 ms 174684 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() { cout << "\n"; }
template<typename T, typename...U>
void dout(T t, U...u) { cout << t << (sizeof...(u) ? ", " : ""), dout(u...); }
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 355;

int n, k;
string s;
int pre[SIZE];
int dp[SIZE][SIZE][SIZE];

int cal(int l, int r, int cur) {
    if (dp[l][r][cur] != -1) return dp[l][r][cur];
    int cnt = pre[n] - (pre[r] - pre[l - 1]) - cur;
    if (cur >= k) dp[l][r][cur] = 0;
    else if (cnt >= k) dp[l][r][cur] = 1;
    else dp[l][r][cur] = (!cal(l, r - 1, cnt) || !cal(l + 1, r, cnt));
    return dp[l][r][cur];
}

void solve() {
    cin >> n >> k;
    cin >> s, s = " " + s;
    FOR (i, 1, n) pre[i] = pre[i - 1] + (s[i] == 'C');
    FOR (i, 1, n) FOR (j, 1, n) FOR (p, 0, n) dp[i][j][p] = -1;
    cout << (cal(1, n, 0) ? "DA" : "NE") << '\n';
}

int main() {
    Waimai;
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10704 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10704 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10704 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10704 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 3 ms 24924 KB Output is correct
8 Correct 3 ms 22876 KB Output is correct
9 Correct 3 ms 24920 KB Output is correct
10 Correct 3 ms 24924 KB Output is correct
11 Correct 3 ms 24924 KB Output is correct
12 Correct 3 ms 24924 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10704 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10704 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 3 ms 24924 KB Output is correct
8 Correct 3 ms 22876 KB Output is correct
9 Correct 3 ms 24920 KB Output is correct
10 Correct 3 ms 24924 KB Output is correct
11 Correct 3 ms 24924 KB Output is correct
12 Correct 3 ms 24924 KB Output is correct
13 Correct 21 ms 174684 KB Output is correct
14 Correct 28 ms 174684 KB Output is correct
15 Correct 21 ms 164444 KB Output is correct
16 Correct 24 ms 172636 KB Output is correct
17 Correct 23 ms 172952 KB Output is correct
18 Correct 21 ms 172624 KB Output is correct