제출 #872584

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

Main

#include <bits/stdc++.h>
#define pb push_back
#define ctoi(x) int(x-'0')
#define cdv(x,y) (((x)+(y)-1)/(y))
#define LOOP(n) for(int rp=0;rp<(n);rp++)
#define sz(x) int(x.size())
#define dbg(x) cout << (#x) << " : " << x << endl;
#define sq(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef long double dl;
const int SZ=2e5+7;
bool dp[350][350][350],vs[350][350][350];
int n,k,p[350],a[350]{};
bool solve(int l,int r,int c){
    if(c==k)return 0;
    int C=(l>0?p[l-1]:0)+p[n-1]-p[r];
    if(C-c==k)return 1;
    if(vs[l][r][c])return dp[l][r][c];
    vs[l][r][c]=1;
    return dp[l][r][c]=!(solve(l+1,r,C-c)&solve(l,r-1,C-c));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tt=1;
    //cin >> tt;
    LOOP(tt){
        cin >> n >> k;
        for(int i=0;i<n;i++){
            char c;cin >> c;
            p[i]=(i>0?p[i-1]:0);
            if(c=='C')p[i]++,a[i]=1;
        }
        cout << (solve(0,n-1,0)?"DA":"NE");
    }
    return 0;
}

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