제출 #1100513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100513		rayan_bd	Kamenčići (COCI21_kamencici)	C++17	0 / 70	1 ms	852 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int ar[400];
int dp[400][400];
int k;
bool fp=1;

int f(int i,int j){
    if(i==j) return ar[i];
    if((j-i)==1) return min(ar[i],ar[j]);
    if(dp[i][j]!=-1) return dp[i][j];
    int ans=min(ar[i]+max(f(i+1,j-1),f(i+2,j)),
        ar[j]+max(f(i+1,j-1),f(i,j-2)));
    return dp[i][j] = ans;
}

int main() {
    


    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
   

    int n;cin>>n>>k;
    string str;
    cin>>str;
    memset(ar,0,sizeof(ar));
    memset(dp,-1,sizeof(dp));
    int tot=0;
    for(int i=0;i<n;++i){
        if(str[i]=='C') ar[i]=1,++tot;
    }
    int f1=f(0,n-1);
    int f2=tot-f1;
    if(f1>f2) cout<<"NE";
    else cout<<"DA";
    return 0;
}

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