oj.uz

Submission #731021

# Submission time Handle Problem Language Result Execution time Memory
731021 2023-04-26T19:30:02 Z murad_2005 Kamenčići (COCI21_kamencici) C++14
70 / 70
 97 ms 175404 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define piii pair<int, pii>
#define pllll pair<ll, ll>
#define plli pair<ll, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define size(v) v.size()
#define INF 2e9
#define f first
#define s second
#define ln "\n"

using namespace std;

const int up = 355;

string s;

int n, k;
int dp[up][up][up], preff[up];

void init(){
    for(int i = 0; i < up; ++i){
        for(int j = 0; j < up; ++j){
            for(int m = 0; m < up; ++m){
                dp[i][j][m] = -1;
            }
        }
    }
}

int win(int l, int r, int red){
    int ok = dp[l][r][red];
    if(ok == -1){
        int total_red = preff[n - 1];
        int red_left = preff[r];
        if(l) red_left -= preff[l - 1];
        int other_red = total_red - red_left - red;
        if(red >= k){
            ok = 0;
        }else if(other_red >= k){
            ok = 1;
        }else{
            if(!win(l + 1, r, other_red) || !win(l, r - 1, other_red)){
                ok = 1;
            }else{
                ok = 0;
            }
        }
        dp[l][r][red] = ok;
    }
    return ok;
}

void solve(){
    cin >> n >> k;
    cin >> s;
    init();
    preff[0] = (s[0] == 'C');
    for(int i = 1; i < n; ++i){
        preff[i] = preff[i - 1] + (s[i] == 'C');
    }
    cout << (win(0, n - 1, 0) ? "DA" : "NE");
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 175304 KB Output is correct
2 Correct 69 ms 175376 KB Output is correct
3 Correct 78 ms 175300 KB Output is correct
4 Correct 70 ms 175312 KB Output is correct
5 Correct 72 ms 175328 KB Output is correct
6 Correct 68 ms 175292 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 175304 KB Output is correct
2 Correct 69 ms 175376 KB Output is correct
3 Correct 78 ms 175300 KB Output is correct
4 Correct 70 ms 175312 KB Output is correct
5 Correct 72 ms 175328 KB Output is correct
6 Correct 68 ms 175292 KB Output is correct
7 Correct 68 ms 175292 KB Output is correct
8 Correct 67 ms 175372 KB Output is correct
9 Correct 66 ms 175284 KB Output is correct
10 Correct 78 ms 175388 KB Output is correct
11 Correct 67 ms 175396 KB Output is correct
12 Correct 66 ms 175308 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 175304 KB Output is correct
2 Correct 69 ms 175376 KB Output is correct
3 Correct 78 ms 175300 KB Output is correct
4 Correct 70 ms 175312 KB Output is correct
5 Correct 72 ms 175328 KB Output is correct
6 Correct 68 ms 175292 KB Output is correct
7 Correct 68 ms 175292 KB Output is correct
8 Correct 67 ms 175372 KB Output is correct
9 Correct 66 ms 175284 KB Output is correct
10 Correct 78 ms 175388 KB Output is correct
11 Correct 67 ms 175396 KB Output is correct
12 Correct 66 ms 175308 KB Output is correct
13 Correct 67 ms 175348 KB Output is correct
14 Correct 77 ms 175404 KB Output is correct
15 Correct 70 ms 175308 KB Output is correct
16 Correct 97 ms 175308 KB Output is correct
17 Correct 70 ms 175344 KB Output is correct
18 Correct 67 ms 175312 KB Output is correct