oj.uz

Submission #527873

# Submission time Handle Problem Language Result Execution time Memory
527873 2022-02-18T14:50:18 Z Jarif_Rahman Kamenčići (COCI21_kamencici) C++17
70 / 70
 234 ms 341800 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;
    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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1336 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1336 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct
13 Correct 216 ms 341800 KB Output is correct
14 Correct 234 ms 339652 KB Output is correct
15 Correct 188 ms 291848 KB Output is correct
16 Correct 210 ms 334072 KB Output is correct
17 Correct 218 ms 335880 KB Output is correct
18 Correct 233 ms 333976 KB Output is correct