oj.uz

Submission #638457

# Submission time Handle Problem Language Result Execution time Memory
638457 2022-09-06T07:29:20 Z NotLinux Kamenčići (COCI21_kamencici) C++14
10 / 70
 1 ms 1364 KB 
/**
 * author: NotLinux
 * created: 06.09.2022 ~ 09:33:06
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
    #include "/home/notlinux/debug.h"
#else
    #define debug(x...) void(37)
#endif
int n,k;string str;
vector<vector<vector<int>>>dp;
vector<int>pre,suff;
//1 = ben yendim , 0 = o yendi
int func(int l,int r,int z){
    if(dp[l][r][z]!=-1)return dp[l][r][z];
    int toplam=pre[l]+suff[n-r-1];
    if((toplam-z)==k){
        dp[l][r][z] = 1;
        return dp[l][r][z];
    }
    else if(z == k){
        dp[l][r][z] = 0;
        return dp[l][r][z];   
    }
    int p1,p2;
    if((l+r)%2==0){
        p1=func(l+1,r,z+(str[l]=='C'));
        p2=func(l,r+1,z+(str[n-r-1]=='C'));
    }
    else {
        p1=func(l+1,r,z);
        p2=func(l,r+1,z);
    }
    if((l+r)%2==0){
        dp[l][r][z] = p1|p2;
    }
    else {
        dp[l][r][z] = p1&p2;
    }
    return dp[l][r][z];
}
void solve(){
    cin>>n>>k>>str;
    dp.assign(n,vector<vector<int>>(n,vector<int>(n,-1)));
    pre.resize(n+1);suff.resize(n+1);
    for(int i=0;i<n;i++)pre[i+1]=pre[i]+(str[i]=='C');
    for(int i=n-1;i>0;i--)suff[i-1]=suff[i]+(str[i-1]=='C');
    cout<<(func(0,0,0)?"DA":"NE")<<endl;    
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    int tt=1;
    //cin >> tt;
    while(tt--)solve();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Incorrect 1 ms 1088 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Incorrect 1 ms 1088 KB Output isn't correct
9 Halted 0 ms 0 KB -