oj.uz

Submission #703979

# Submission time Handle Problem Language Result Execution time Memory
703979 2023-03-01T08:07:31 Z KazmetreD Kamenčići (COCI21_kamencici) C++17
70 / 70
 146 ms 242972 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "debug.h"
#else
#define debug(x) void(37)
#endif

#define lsb(x) ((x)&(-x))
#define all(x) x.begin(),x.end()
#define setprec(n) cout << fixed << showpoint;cout << setprecision(n);
typedef long long ll;
typedef long double ld;
const ld eps = 1e-10;
const ll MOD1 = 1e9+7;
const ll MOD2 = 998244353;
const ll LINF = 1e18;
const int IINF = 1e9;
#define int ll

const int maxn = 355;
int n, k;
string str;
int dp[maxn][maxn][maxn];
int cm[maxn][maxn][maxn];
vector<int> pref, suff;

int go(int l, int r, int tk){
    int turn = (n-(r-l)) % 2;
    if(turn){ // branka's turn
        int br = (suff[r] + pref[l]) - tk;
        if(br >= k) return 0;
        if(tk >= k) return 1;

        int can = 0;
        if(str[l] == 'C' && br + 1 < k) can |= !go(l+1, r, tk);
        else if(str[l] != 'C') can |= !go(l+1, r, tk);

        if(str[r-1] == 'C' && br + 1 < k) can |= !go(l, r-1, tk);
        else if(str[r-1] != 'C') can |= !go(l, r-1, tk);
    
        return can;
    }
    else{ // anton's turn
        if(tk >= k) return 0;
        if((suff[r] + pref[l]) - tk >= k) return 1;
        if(cm[l][r][tk]) return dp[l][r][tk];

        int can = 0;
        if(str[l] == 'C' && tk + 1 < k) can |= !go(l+1, r, tk+1);
        else if(str[l] != 'C') can |= !go(l+1, r, tk);

        if(str[r-1] == 'C' && tk + 1 < k) can |= !go(l, r-1, tk+1);
        else if(str[r-1] != 'C') can |= !go(l, r-1, tk);
    
        cm[l][r][tk] = 1;
        return dp[l][r][tk] = can;
    }
}

void solve(){
    cin >> n >> k;
    cin >> str;

    pref.resize(n+1), suff.resize(n+1);
    for(int i = 1;i <= n;i++) pref[i] = pref[i-1] + (str[i-1] == 'C');
    for(int i = n-1;i >= 0;i--) suff[i] = suff[i+1] + (str[i] == 'C');

    if(go(0, n, 0)) cout << "DA" << "\n";
    else cout << "NE" << "\n";
}


signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    mt19937 mt(time(NULL));
    //setprec(10);

    //freopen("sleepy.in", "r", stdin);
    //freopen("in.txt", "w", stdout);

    int t = 1;
    //cin >> t;
    for(int i = 1;i <= t;i++)
        solve();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 836 KB Output is correct
9 Correct 1 ms 2516 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 2004 KB Output is correct
12 Correct 3 ms 4564 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 836 KB Output is correct
9 Correct 1 ms 2516 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 2004 KB Output is correct
12 Correct 3 ms 4564 KB Output is correct
13 Correct 3 ms 6356 KB Output is correct
14 Correct 146 ms 236972 KB Output is correct
15 Correct 42 ms 74648 KB Output is correct
16 Correct 107 ms 149576 KB Output is correct
17 Correct 123 ms 242972 KB Output is correct
18 Correct 50 ms 94320 KB Output is correct