oj.uz

Submission #547251

# Submission time Handle Problem Language Result Execution time Memory
547251 2022-04-10T05:02:20 Z MahfuzAhmed Kamenčići (COCI21_kamencici) C++14
70 / 70
 58 ms 122548 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 352;
 
int n, k;
int prefix_sum[maxn];
int dp[maxn][maxn][maxn];
 
 
int get_ans(int l, int r, int v){
    int& res = dp[l][r][v];
 
    if(res == -1){
        int red = prefix_sum[n - 1];
        int left = prefix_sum[r];
        if(l) left -= prefix_sum[l - 1];
 
        int other = red - left - v;
 
        if(v >= k)
            res = 0;
        else if(other >= k)
            res = 1;
        else
            if(!get_ans(l + 1, r, other) || !get_ans(l, r - 1, other))
                res = 1;
            else
                res = 0;
    }
 
    return res;
}
 
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> k;
    string str; cin >> str;
 
    fill_n(&dp[0][0][0], 352 * 352 * 252, -1);
 
    prefix_sum[0] = (str[0] == 'C');
    for(int i = 1; i < n; i++)
        prefix_sum[i] = prefix_sum[i - 1] + (str[i] == 'C');
 
    if(get_ans(0, n -1, 0))
        cout << "DA\n";
    else
        cout << "NE\n";
 
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 122496 KB Output is correct
2 Correct 46 ms 122448 KB Output is correct
3 Correct 54 ms 122444 KB Output is correct
4 Correct 54 ms 122476 KB Output is correct
5 Correct 47 ms 122460 KB Output is correct
6 Correct 47 ms 122472 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 122496 KB Output is correct
2 Correct 46 ms 122448 KB Output is correct
3 Correct 54 ms 122444 KB Output is correct
4 Correct 54 ms 122476 KB Output is correct
5 Correct 47 ms 122460 KB Output is correct
6 Correct 47 ms 122472 KB Output is correct
7 Correct 44 ms 122452 KB Output is correct
8 Correct 46 ms 122536 KB Output is correct
9 Correct 49 ms 122428 KB Output is correct
10 Correct 45 ms 122428 KB Output is correct
11 Correct 45 ms 122440 KB Output is correct
12 Correct 58 ms 122420 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 122496 KB Output is correct
2 Correct 46 ms 122448 KB Output is correct
3 Correct 54 ms 122444 KB Output is correct
4 Correct 54 ms 122476 KB Output is correct
5 Correct 47 ms 122460 KB Output is correct
6 Correct 47 ms 122472 KB Output is correct
7 Correct 44 ms 122452 KB Output is correct
8 Correct 46 ms 122536 KB Output is correct
9 Correct 49 ms 122428 KB Output is correct
10 Correct 45 ms 122428 KB Output is correct
11 Correct 45 ms 122440 KB Output is correct
12 Correct 58 ms 122420 KB Output is correct
13 Correct 47 ms 122412 KB Output is correct
14 Correct 57 ms 122548 KB Output is correct
15 Correct 48 ms 122528 KB Output is correct
16 Correct 54 ms 122472 KB Output is correct
17 Correct 49 ms 122512 KB Output is correct
18 Correct 47 ms 122420 KB Output is correct