oj.uz

Submission #494315

# Submission time Handle Problem Language Result Execution time Memory
494315 2021-12-15T05:58:26 Z ktkerem Kamenčići (COCI21_kamencici) C++17
70 / 70
 250 ms 341812 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll _i=0;
#define ffn(x) _i=x
#define llll pair<ll , ll>
#define stitr set<llll>::iterator
#define fora(y,x) for(ll y=_i;x>y;y++)
#define pb push_back
#define pf push_front
#define debu cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e13 + 7; 
const ll ous=1e6 + 5;
const ll dx[4] = {1 , -1 , 0 , 0} , dy[4] = {0,0,-1,1};
ll dp[352][352][352] , pref[352] , n , k;
string h;
ll fun(ll l , ll r , ll ot){
    ll &res = dp[l][r][ot];
    if(res == -1){
        ll tr = pref[n-1] , rl = pref[r];
        if(l > 0){
            rl-= pref[l-1];
        }
        ll ots =tr - rl - ot;
        if(ot >= k){
            res = 0;
        }
        else if(ots >= k){
            res = 1;
        }
        else{
            if(!fun(l+1 , r , ots) || !fun(l , r-1 , ots)){
                res = 1;
            }
            else{
                res = 0;
            }
        }
    }
    return res;
}
void solve(){
    memset(dp , -1 , sizeof(dp));
    cin >> n >> k >> h;
    pref[0] = (h[0] == 'C');
    for(ll i=1;n>i;i++){
        pref[i] = pref[i-1] + (h[i]=='C'); 
    }
    if(fun(0 , n-1 , 0)){
        cout << "DA\n";
    }
    else{
        cout << "NE\n";
    }
    return;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll t=1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 341660 KB Output is correct
2 Correct 131 ms 341704 KB Output is correct
3 Correct 138 ms 341736 KB Output is correct
4 Correct 156 ms 341588 KB Output is correct
5 Correct 129 ms 341576 KB Output is correct
6 Correct 134 ms 341812 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 341660 KB Output is correct
2 Correct 131 ms 341704 KB Output is correct
3 Correct 138 ms 341736 KB Output is correct
4 Correct 156 ms 341588 KB Output is correct
5 Correct 129 ms 341576 KB Output is correct
6 Correct 134 ms 341812 KB Output is correct
7 Correct 137 ms 341644 KB Output is correct
8 Correct 138 ms 341612 KB Output is correct
9 Correct 135 ms 341704 KB Output is correct
10 Correct 131 ms 341596 KB Output is correct
11 Correct 134 ms 341700 KB Output is correct
12 Correct 134 ms 341624 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 341660 KB Output is correct
2 Correct 131 ms 341704 KB Output is correct
3 Correct 138 ms 341736 KB Output is correct
4 Correct 156 ms 341588 KB Output is correct
5 Correct 129 ms 341576 KB Output is correct
6 Correct 134 ms 341812 KB Output is correct
7 Correct 137 ms 341644 KB Output is correct
8 Correct 138 ms 341612 KB Output is correct
9 Correct 135 ms 341704 KB Output is correct
10 Correct 131 ms 341596 KB Output is correct
11 Correct 134 ms 341700 KB Output is correct
12 Correct 134 ms 341624 KB Output is correct
13 Correct 137 ms 341676 KB Output is correct
14 Correct 146 ms 341696 KB Output is correct
15 Correct 134 ms 341672 KB Output is correct
16 Correct 146 ms 341612 KB Output is correct
17 Correct 139 ms 341704 KB Output is correct
18 Correct 136 ms 341636 KB Output is correct