Submission #900162

#	Time	Username	Problem	Language	Result	Execution time	Memory
900162		mariaclara	Kamenčići (COCI21_kamencici)	C++17	70 / 70	26 ms	41816 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
#define all(x) x.begin(), x.end()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, k, prefix[500], sufix[500];
string s;
bool dp[350][350][350]; // l, r, C pegos

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> s;
    
    for(int i = 1; i <= n; i++)
        prefix[i] = prefix[i-1] + (s[i-1] == 'C');

    for(int i = 1; i <= n; i++)
        sufix[i] = prefix[n] - prefix[i-1];

    for(int tam = 1; tam <= n; tam++) { // tamanho do intervalo
        for(int l = 0; l + tam <= n; l++) {
            int r = l+tam-1;

            for(int C = 0; C < k; C++) { // quantos eu coletei até agr
                if(l == r) {
                    dp[l][r][C] = C+1 < k;
                    continue;
                }

                // dp[l+1][r]
                int a = prefix[l] + sufix[r+2] - C;
                if(a >= 0 and dp[l+1][r][a] == 0) dp[l][r][C] = 1;
                // dp[l][r-1]
                if(a >= 0 and dp[l][r-1][a] == 0) dp[l][r][C] = 1;

                //cout << "[ " << l << ", " << r << ", " << C << ", " << a << ", " << b << " ] = " << dp[l][r][C] << "\n";
            }
        }
    } 

    if(dp[0][n-1][0]) cout << "DA\n";
    else cout << "NE\n";
}

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