Submission #742117

#	Time	Username	Problem	Language	Result	Execution time	Memory
742117		Ahmed57	Kamenčići (COCI21_kamencici)	C++17	70 / 70	173 ms	338892 KiB

Main

#include <bits/stdc++.h>

using namespace std;
int dp[351][351][351][2];
string s;int k,n;
int pref[351],suff[355];
long long solve(int i,int j,int took,int turn){
    if(took>=k)return 1;
    if((i==0?0:pref[i-1])+(suff[j+1])-took>=k)return 0;
    if(dp[i][j][took][turn]!=-1)return dp[i][j][took][turn];
    if(turn==0){
        return dp[i][j][took][turn] = min(solve(i+1,j,took+(s[i]=='C'?1:0),!turn),solve(i,j-1,took+(s[j]=='C'?1:0),!turn));
    }else{
        return dp[i][j][took][turn] = max(solve(i+1,j,took,!turn),solve(i,j-1,took,!turn));
    }
}
signed main(){
    memset(dp,-1,sizeof dp);
    cin>>n>>k;
    cin>>s;
    for(int i = 0;i<s.size();i++){
        pref[i] = (s[i]=='C'?1:0);
        if(i)pref[i]+=pref[i-1];
    }
    for(int i = s.size()-1;i>=0;i--){
        suff[i] = (s[i]=='C'?1:0);
        if(i<s.size()-1)suff[i]+=suff[i+1];
    }
    cout<<(solve(0,s.size()-1,0,0)==0?"DA":"NE")<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0;i<s.size();i++){
      |                   ~^~~~~~~~~
Main.cpp:27:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if(i<s.size()-1)suff[i]+=suff[i+1];
      |            ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40