Submission #717355

#	Time	Username	Problem	Language	Result	Execution time	Memory
717355		TheSahib	Kamenčići (COCI21_kamencici)	C++17	70 / 70	75 ms	169568 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 351;

int n, k; 
string s;

int reds[MAX];
int dp[MAX][MAX][MAX];

bool f(int l, int r, int red){
    if(dp[l][r][red] != -1) return dp[l][r][red];
    if(red >= k) return 0;
    int red1 = reds[n] - (reds[r] - reds[l - 1]) - red;
    if(red1 >= k) return 1;
    if(l == r) return 0;


    if(f(l + 2, r, red + (s[l] == 'C')) && f(l + 1, r - 1, red + (s[l] == 'C'))) return dp[l][r][red] = 1;

    if(f(l, r - 2, red + (s[r] == 'C')) && f(l + 1, r - 1, red + (s[r] == 'C'))) return dp[l][r][red] = 1;

    return dp[l][r][red] = 0;
}

void solve(){
    memset(dp, -1, sizeof(dp));
    cin >> n >> k;
    cin >> s;
    s.insert(s.begin(), ' ');

    for (int i = 1; i <= n; i++)
    {
        reds[i] = reds[i - 1] + (s[i] == 'C');
    }

    if(f(1, n, 0)){
        cout << "DA\n";
    }
    else{
        cout << "NE\n";
    }
}

int main()
{
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'bool f(int, int, int)':
Main.cpp:25:103: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   25 |     if(f(l + 2, r, red + (s[l] == 'C')) && f(l + 1, r - 1, red + (s[l] == 'C'))) return dp[l][r][red] = 1;
      |                                                                                         ~~~~~~~~~~~~~~^~~
Main.cpp:27:103: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |     if(f(l, r - 2, red + (s[r] == 'C')) && f(l + 1, r - 1, red + (s[r] == 'C'))) return dp[l][r][red] = 1;
      |                                                                                         ~~~~~~~~~~~~~~^~~
Main.cpp:29:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   29 |     return dp[l][r][red] = 0;
      |            ~~~~~~~~~~~~~~^~~

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