oj.uz

Submission #638556

# Submission time Handle Problem Language Result Execution time Memory
638556 2022-09-06T11:23:18 Z NotLinux Kamenčići (COCI21_kamencici) C++14
10 / 70
 1 ms 1748 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;
//state of a game is  1 if I won this state
//state of a game is  0 if I lost this state
int func(int l,int r,int z){
  	if(l+r > n)return 0;
    if(dp[l][r][z]!=-1)return dp[l][r][z];//using dp optimization
 
    int toplam=pre[l]+suff[n-r-1];//number of the red pebbles in the range [0,l] + [r,n]
    //now we check if the game ends this turn
    if((toplam-z)==k){//has the opponent lost
        dp[l][r][z] = 1;
        return dp[l][r][z];//return that I won in this state
    }
    else if(z == k){//have I lost
        dp[l][r][z] = 0;
        return dp[l][r][z];//return that I lost in this state
    }
 
    //now we check what happens if we go from one of two cases : p1 and p2
    int p1,p2;//two possible cases
    if((l+r)%2==0){//is this my turn
        p1=func(l+1,r,z+(str[l]=='C'));//what happens if I take from left
        p2=func(l,r+1,z+(str[n-r-1]=='C'));//what happens if I take from right
    }
    else {//is this his turn
        p1=func(l+1,r,z);//what happens if he takes from left
        p2=func(l,r+1,z);//what happens if he takes from right
    }
 
 
    //if I won in p1 or p2 , than I won in this state , else I lost in this state , same logic for the opponent
    if((l+r)%2==0){//is this my turn
        dp[l][r][z] = p1|p2;//choose the optimal for urself
    }
    else {//is this his turn
        dp[l][r][z] = p1&p2;//he chooses optimal for himself
    }
 
 
    return dp[l][r][z];//return the state of the game
}
void solve(){
    cin>>n>>k>>str;
 
    dp.assign(n+5,vector<vector<int>>(n+5,vector<int>(n+5,-1)));
    pre.resize(n+1);suff.resize(n+1);
 
    for(int i=0;i<n;i++)pre[i+1]=pre[i]+(str[i]=='C');//building the prefix array
    for(int i=n-1;i>0;i--)suff[i-1]=suff[i]+(str[i-1]=='C');//building the suffix array
 
    cout<<(func(0,0,0)?"DA":"NE")<<endl;//if I won print DA
}
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 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 40.0

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