oj.uz

Submission #527908

# Submission time Handle Problem Language Result Execution time Memory
527908 2022-02-18T17:03:25 Z Jarif_Rahman Kamenčići (COCI21_kamencici) C++17
70 / 70
 286 ms 172332 KB 
#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;
    string s; cin >> s;

    vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n, 0)));

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

    for(int sz = 2; sz <= n; sz++) for(int i = 0; i+sz-1 < n; i++){
        int j = i+sz-1;

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

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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 312 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 836 KB Output is correct
10 Correct 1 ms 696 KB Output is correct
11 Correct 1 ms 692 KB Output is correct
12 Correct 1 ms 696 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 2 ms 836 KB Output is correct
10 Correct 1 ms 696 KB Output is correct
11 Correct 1 ms 692 KB Output is correct
12 Correct 1 ms 696 KB Output is correct
13 Correct 272 ms 172332 KB Output is correct
14 Correct 278 ms 171480 KB Output is correct
15 Correct 229 ms 148292 KB Output is correct
16 Correct 256 ms 169500 KB Output is correct
17 Correct 286 ms 170488 KB Output is correct
18 Correct 274 ms 169504 KB Output is correct