oj.uz

Submission #862192

# Submission time Handle Problem Language Result Execution time Memory
862192 2023-10-17T16:28:37 Z 3omar_ahmed Kamenčići (COCI21_kamencici) C++17
70 / 70
 98 ms 344776 KB 
#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()

int n, k;
string x;
vector < int > pre, suf;

int dp[353][353][353];

int solve(int l, int r, int red) {
    int type = ((l - 1) + (n - r)) % 2;
    if(red == k) {
        return 0;
    }
    int opp = pre[l - 1] + suf[r + 1] - red;
    if(opp == k) {  
        return 1;
    }
    if(dp[l][r][red] != -1) return dp[l][r][red]; 
    dp[l][r][red] = 0;
    if(type == 0) {
        if(solve(l + 1, r, red + (x[l] == 'C')))
            return dp[l][r][red] = 1;
        if(solve(l, r - 1, red + (x[r] == 'C')))
            return dp[l][r][red] = 1;
        return 0;
    } else {
        if(!solve(l + 1, r, red))
            return 0;
        if(!solve(l, r - 1, red))
            return 0;
        return dp[l][r][red] = 1;
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    cin >> n >> k >> x;
    pre = suf = vector < int > (n + 2);
    x = "%" + x;
    for(int i = 1 ; i <= n ; i++) {
        pre[i] = pre[i - 1] + (x[i] == 'C');
    }
    for(int i = n ; i >= 1 ; i--) {
        suf[i] = suf[i + 1] + (x[i] == 'C');
    }
    memset(dp, -1, sizeof(dp));
    if(solve(1, n, 0)) {
        cout << "DA" << endl; 
    } else {
        cout << "NE" << endl;
    }
    return 0 ;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 344660 KB Output is correct
2 Correct 98 ms 344760 KB Output is correct
3 Correct 91 ms 344564 KB Output is correct
4 Correct 82 ms 344572 KB Output is correct
5 Correct 83 ms 344688 KB Output is correct
6 Correct 83 ms 344712 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 344660 KB Output is correct
2 Correct 98 ms 344760 KB Output is correct
3 Correct 91 ms 344564 KB Output is correct
4 Correct 82 ms 344572 KB Output is correct
5 Correct 83 ms 344688 KB Output is correct
6 Correct 83 ms 344712 KB Output is correct
7 Correct 83 ms 344660 KB Output is correct
8 Correct 91 ms 344660 KB Output is correct
9 Correct 82 ms 344740 KB Output is correct
10 Correct 81 ms 344608 KB Output is correct
11 Correct 84 ms 344752 KB Output is correct
12 Correct 95 ms 344644 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 344660 KB Output is correct
2 Correct 98 ms 344760 KB Output is correct
3 Correct 91 ms 344564 KB Output is correct
4 Correct 82 ms 344572 KB Output is correct
5 Correct 83 ms 344688 KB Output is correct
6 Correct 83 ms 344712 KB Output is correct
7 Correct 83 ms 344660 KB Output is correct
8 Correct 91 ms 344660 KB Output is correct
9 Correct 82 ms 344740 KB Output is correct
10 Correct 81 ms 344608 KB Output is correct
11 Correct 84 ms 344752 KB Output is correct
12 Correct 95 ms 344644 KB Output is correct
13 Correct 82 ms 344712 KB Output is correct
14 Correct 91 ms 344776 KB Output is correct
15 Correct 84 ms 344564 KB Output is correct
16 Correct 90 ms 344548 KB Output is correct
17 Correct 94 ms 344656 KB Output is correct
18 Correct 92 ms 344656 KB Output is correct