oj.uz

Submission #487130

# Submission time Handle Problem Language Result Execution time Memory
487130 2021-11-14T13:53:52 Z JovanB Kamenčići (COCI21_kamencici) C++17
70 / 70
 34 ms 22872 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 350;

bool dp[N+5][N+5][N+5];
int pre[N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    for(int i=1; i<=n; i++){
        if(s[i-1] == 'C') pre[i]++;
        pre[i] += pre[i-1];
    }
    for(int len=1; len<=n; len++){
        for(int l=1; l+len-1<=n; l++){
            int r = l + len - 1;
            int svi = pre[n] - pre[r] + pre[l-1];
            for(int j=0; j<=svi; j++){
                if(j >= k) continue;
                if(svi - j >= k){
                    dp[l][r][j] = 1;
                    continue;
                }
                if(s[l-1] == 'C' && j+1 < k && !dp[l+1][r][svi - j]) dp[l][r][j] = 1;
                if(s[l-1] == 'P' && !dp[l+1][r][svi - j]) dp[l][r][j] = 1;
                if(s[r-1] == 'C' && j+1 < k && !dp[l][r-1][svi - j]) dp[l][r][j] = 1;
                if(s[r-1] == 'P' && !dp[l][r-1][svi - j]) dp[l][r][j] = 1;
            }
        }
    }
    if(dp[1][n][0]) cout << "DA\n";
    else cout << "NE\n";
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 844 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Correct 17 ms 22872 KB Output is correct
14 Correct 16 ms 22728 KB Output is correct
15 Correct 10 ms 20684 KB Output is correct
16 Correct 24 ms 22532 KB Output is correct
17 Correct 34 ms 22652 KB Output is correct
18 Correct 20 ms 22604 KB Output is correct