oj.uz

Submission #866889

# Submission time Handle Problem Language Result Execution time Memory
866889 2023-10-27T09:34:11 Z 3as8 Kamenčići (COCI21_kamencici) C++14
70 / 70
 63 ms 193336 KB 
#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define fastIO cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);

#define mid ((l + r) / 2)
#define lChild ((index * 2) + 1)
#define rChild ((index * 2) + 2)

using namespace std;

struct node {
    ll t, a, b;
};

ll dp[351][351][200];

bool get(string& s, ll l, ll r, ll k, vector<ll>& score, bool round) {

   /* cout<<round + 1<< " => "<<l<<" "<<r<<endl;
    cout<<"Score: "<<score[0]<<" "<<score[1]<<endl;*/

    if(score[0] == k) return false;
    else if(score[1] == k) return true;

    if(dp[l][r][score[0]] != -1) return dp[l][r][score[0]];

    bool ans = round;
    score[round] += s[l] == 'C';
    if(!round) ans |= get(s, l + 1, r, k, score, !round);
    else ans &= get(s, l + 1, r, k, score, !round);
    score[round] -= s[l] == 'C';


    score[round] += s[r] == 'C';
    if(!round) ans |= get(s, l, r - 1, k, score, !round);
    else ans &= get(s, l, r - 1, k, score, !round);
    score[round] -= s[r] == 'C';

    return dp[l][r][score[0]] = ans;
}



void solve(ll _) {

    ll n, k; cin>>n>>k;

    memset(dp, -1, sizeof dp);
    string s; cin>>s;

    vector<ll> scores = {0, 0};
    cout<<(get(s, 0, n - 1, k, scores, 0) ? "DA" : "NE")<<endl;

}

int main() {
    fastIO

    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);

    ll t = 0;  solve(t);
}

Compilation message

Main.cpp: In function 'bool get(std::string&, long long int, long long int, long long int, std::vector<long long int>&, bool)':
Main.cpp:41:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   41 |     return dp[l][r][score[0]] = ans;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 193104 KB Output is correct
2 Correct 40 ms 193108 KB Output is correct
3 Correct 38 ms 193104 KB Output is correct
4 Correct 39 ms 193104 KB Output is correct
5 Correct 39 ms 193304 KB Output is correct
6 Correct 39 ms 193108 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 193104 KB Output is correct
2 Correct 40 ms 193108 KB Output is correct
3 Correct 38 ms 193104 KB Output is correct
4 Correct 39 ms 193104 KB Output is correct
5 Correct 39 ms 193304 KB Output is correct
6 Correct 39 ms 193108 KB Output is correct
7 Correct 38 ms 193104 KB Output is correct
8 Correct 39 ms 193116 KB Output is correct
9 Correct 38 ms 193276 KB Output is correct
10 Correct 38 ms 193308 KB Output is correct
11 Correct 37 ms 193160 KB Output is correct
12 Correct 37 ms 193108 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 193104 KB Output is correct
2 Correct 40 ms 193108 KB Output is correct
3 Correct 38 ms 193104 KB Output is correct
4 Correct 39 ms 193104 KB Output is correct
5 Correct 39 ms 193304 KB Output is correct
6 Correct 39 ms 193108 KB Output is correct
7 Correct 38 ms 193104 KB Output is correct
8 Correct 39 ms 193116 KB Output is correct
9 Correct 38 ms 193276 KB Output is correct
10 Correct 38 ms 193308 KB Output is correct
11 Correct 37 ms 193160 KB Output is correct
12 Correct 37 ms 193108 KB Output is correct
13 Correct 37 ms 193116 KB Output is correct
14 Correct 63 ms 193288 KB Output is correct
15 Correct 40 ms 193108 KB Output is correct
16 Correct 63 ms 193328 KB Output is correct
17 Correct 48 ms 193336 KB Output is correct
18 Correct 40 ms 193188 KB Output is correct