oj.uz

Submission #731020

# Submission time Handle Problem Language Result Execution time Memory
731020 2023-04-26T19:28:51 Z murad_2005 Kamenčići (COCI21_kamencici) C++14
10 / 70
 1000 ms 175408 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][k];
    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 69 ms 175392 KB Output is correct
2 Correct 75 ms 175352 KB Output is correct
3 Correct 75 ms 175296 KB Output is correct
4 Correct 65 ms 175284 KB Output is correct
5 Correct 67 ms 175368 KB Output is correct
6 Correct 69 ms 175320 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 175392 KB Output is correct
2 Correct 75 ms 175352 KB Output is correct
3 Correct 75 ms 175296 KB Output is correct
4 Correct 65 ms 175284 KB Output is correct
5 Correct 67 ms 175368 KB Output is correct
6 Correct 69 ms 175320 KB Output is correct
7 Correct 66 ms 175340 KB Output is correct
8 Correct 66 ms 175348 KB Output is correct
9 Correct 79 ms 175352 KB Output is correct
10 Correct 66 ms 175280 KB Output is correct
11 Correct 75 ms 175304 KB Output is correct
12 Execution timed out 1048 ms 175408 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 175392 KB Output is correct
2 Correct 75 ms 175352 KB Output is correct
3 Correct 75 ms 175296 KB Output is correct
4 Correct 65 ms 175284 KB Output is correct
5 Correct 67 ms 175368 KB Output is correct
6 Correct 69 ms 175320 KB Output is correct
7 Correct 66 ms 175340 KB Output is correct
8 Correct 66 ms 175348 KB Output is correct
9 Correct 79 ms 175352 KB Output is correct
10 Correct 66 ms 175280 KB Output is correct
11 Correct 75 ms 175304 KB Output is correct
12 Execution timed out 1048 ms 175408 KB Time limit exceeded
13 Halted 0 ms 0 KB -