제출 #987932

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

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, k;
string s;
vector<int> v;
vector<vector<vector<int>>> dp(350, vector<vector<int>>(350, vector<int>(350, -1)));
int f(int i, int j, int x, int als){
    if (x >= k){
        return 0;
    }
    else if (als >= k){
        dp[i][j][x] = 1;
    }
    else if (dp[i][j][x] != -1){
        return dp[i][j][x];
    }
    else if (i == j){
        if (s[i] == 'C'){
            x++;
        }
        if (x < k){
            dp[i][j][x] = 1;
        }
        else{
            dp[i][j][x] = 0;
        }
    }
    else if (i == j - 1){
        int x1 = x + v[i];
        int x2 = x + v[j];
        if (x1 < k || x2 < k){
            dp[i][j][x] = 1;
        }
        else{
            dp[i][j][x] = 0;
        }
    }
    else{
        dp[i][j][x] = max(min(f(i + 1, j - 1, x + v[i], als + v[j]), f(i + 2, j, x + v[i], als + v[i + 1])),
                          min(f(i + 1, j - 1, x + v[j], als + v[i]), f(i, j - 2, x + v[j], als + v[j - 1])));
    }
    return dp[i][j][x];
}
int main(){
    cin>>n>>k;
    cin>>s;
    for (int i = 0; i < n; i++){
        if (s[i] == 'C'){
            v.push_back(1);
        }
        else{
            v.push_back(0);
        }
    }
    int ans = f(0, n - 1, 0, 0);
    if (ans == 1){
        cout<<"DA";
    }
    else{
        cout<<"NE";
    }
}

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