oj.uz

Submission #900162

# Submission time Handle Problem Language Result Execution time Memory
900162 2024-01-07T19:07:05 Z mariaclara Kamenčići (COCI21_kamencici) C++17
70 / 70
 26 ms 41816 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6616 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6616 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 15 ms 41816 KB Output is correct
14 Correct 10 ms 41564 KB Output is correct
15 Correct 8 ms 41504 KB Output is correct
16 Correct 18 ms 41620 KB Output is correct
17 Correct 26 ms 41564 KB Output is correct
18 Correct 17 ms 41560 KB Output is correct