Submission #527873

#	Time	Username	Problem	Language	Result	Execution time	Memory
527873		Jarif_Rahman	Kamenčići (COCI21_kamencici)	C++17	70 / 70	234 ms	341800 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k; cin >> n >> k;
    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(n+1, 0)));

    str s; cin >> s;

    for(int i = 0; i < n; i++){
        if(s[i] == 'C' && n%2 == 1) for(int kk = 0; kk <= n; kk++) dp[i][i][kk] = 1;
    }

    for(int sz = 2; sz <= n; sz++) for(int i = 0, j = sz-1; j < n; i++, j++){
        for(int kk = 0; kk <= n; kk++){
            if(kk != 0) dp[i][j][kk] = dp[i][j][kk-1];

            if(s[i] == 'C' && s[j] == 'C'){
                if((n-sz)%2 == 0){
                    ll cur = 0;
                    if(kk != 0) cur = max(dp[i+1][j][kk-1], dp[i][j-1][kk-1]);
                    dp[i][j][kk] = max(dp[i][j][kk], cur);
                }
                else{
                    ll cur = min(dp[i+1][j][kk], dp[i][j-1][kk])+1;
                    dp[i][j][kk] = max(dp[i][j][kk], cur);
                }
            }
            else if(s[i] == 'C'){
                if((n-sz)%2 == 0){
                    ll cur = dp[i][j-1][kk];
                    if(kk != 0) cur = max(cur, dp[i+1][j][kk-1]);
                    dp[i][j][kk] = max(dp[i][j][kk], cur);
                }
                else{
                    ll cur = min(dp[i+1][j][kk]+1, dp[i][j-1][kk]);
                    dp[i][j][kk] = max(dp[i][j][kk], cur);
                }
            }
            else if(s[j] == 'C'){
                if((n-sz)%2 == 0){
                    ll cur = dp[i+1][j][kk];
                    if(kk != 0) cur = max(cur, dp[i][j-1][kk-1]);
                    dp[i][j][kk] = max(dp[i][j][kk], cur);
                }
                else{
                    ll cur = min(dp[i+1][j][kk], dp[i][j-1][kk]+1);
                    dp[i][j][kk] = max(dp[i][j][kk], cur);
                }
            }
            else{
                if((n-sz)%2 == 0){
                    ll cur = max(dp[i+1][j][kk], dp[i][j-1][kk]);
                    dp[i][j][kk] = max(dp[i][j][kk], cur);
                }
                else{
                    ll cur = min(dp[i+1][j][kk], dp[i][j-1][kk]);
                    dp[i][j][kk] = max(dp[i][j][kk], cur);
                }
            }
        }
    }

    cout << (dp[0][n-1][k-1] >= k ? "DA\n":"NE\n");

}

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