oj.uz

Submission #731017

# Submission time Handle Problem Language Result Execution time Memory
731017 2023-04-26T19:27:02 Z murad_2005 Kamenčići (COCI21_kamencici) C++14
30 / 70
 1000 ms 175412 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 k = 0; k < up; ++k){
                dp[i][j][k] = -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;
            }
        }
    }
    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 70 ms 175308 KB Output is correct
2 Correct 69 ms 175368 KB Output is correct
3 Correct 66 ms 175288 KB Output is correct
4 Correct 68 ms 175412 KB Output is correct
5 Correct 69 ms 175324 KB Output is correct
6 Correct 72 ms 175372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 175308 KB Output is correct
2 Correct 69 ms 175368 KB Output is correct
3 Correct 66 ms 175288 KB Output is correct
4 Correct 68 ms 175412 KB Output is correct
5 Correct 69 ms 175324 KB Output is correct
6 Correct 72 ms 175372 KB Output is correct
7 Correct 80 ms 175412 KB Output is correct
8 Correct 69 ms 175308 KB Output is correct
9 Correct 78 ms 175352 KB Output is correct
10 Correct 67 ms 175392 KB Output is correct
11 Correct 89 ms 175308 KB Output is correct
12 Correct 638 ms 175408 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 175308 KB Output is correct
2 Correct 69 ms 175368 KB Output is correct
3 Correct 66 ms 175288 KB Output is correct
4 Correct 68 ms 175412 KB Output is correct
5 Correct 69 ms 175324 KB Output is correct
6 Correct 72 ms 175372 KB Output is correct
7 Correct 80 ms 175412 KB Output is correct
8 Correct 69 ms 175308 KB Output is correct
9 Correct 78 ms 175352 KB Output is correct
10 Correct 67 ms 175392 KB Output is correct
11 Correct 89 ms 175308 KB Output is correct
12 Correct 638 ms 175408 KB Output is correct
13 Execution timed out 1081 ms 175320 KB Time limit exceeded
14 Halted 0 ms 0 KB -