제출 #1004798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1004798		DangerNoodle7591	Kamenčići (COCI21_kamencici)	C++17	70 / 70	22 ms	84828 KiB

Main

#include  <bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
//#define int long long int
//#define ll long long
#define pb push_back
#define p push
#define f first
#define s second
#define N 350
int arr[N];
int dp[N][N][N/2+1];//l r biz_kaç_red
int n,k;
inline int red_blue(int l,int r,int biz,int o,int sira){
  if(dp[l][r][biz]!=-1)return dp[l][r][biz];
  if(biz==k)return 0;
  if(o==k)return 1;
  if(sira){//bizde
    int sol=red_blue(l,r-1,biz+arr[r],o,0),sag=red_blue(l+1,r,biz+arr[l],o,0);
    dp[l][r][biz]=max(sag,sol);
    return dp[l][r][biz];
  }

  int sol=red_blue(l,r-1,biz,o+arr[r],1),sag=red_blue(l+1,r,biz,o+arr[l],1);
  dp[l][r][biz]=min(sol,sag);
  return dp[l][r][biz];
}
signed main(){
  lalala;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    char a;cin>>a;
    if(a=='C') arr[i]=1;
  }
  memset(dp,-1,sizeof(dp));
  int a=red_blue(0,n-1,0,0,1);
  if(a)cout<<"DA"<<endl;
  else cout<<"NE"<<endl;
 
}

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