oj.uz

Submission #987932

# Submission time Handle Problem Language Result Execution time Memory
987932 2024-05-23T19:37:52 Z HasanV11010238 Kamenčići (COCI21_kamencici) C++17
70 / 70
 181 ms 172572 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, k;
string s;
vector<int> v;
vector<vector<vector<int>>> dp(350, vector<vector<int>>(350, vector<int>(350, -1)));
int f(int i, int j, int x, int als){
    if (x >= k){
        return 0;
    }
    else if (als >= k){
        dp[i][j][x] = 1;
    }
    else if (dp[i][j][x] != -1){
        return dp[i][j][x];
    }
    else if (i == j){
        if (s[i] == 'C'){
            x++;
        }
        if (x < k){
            dp[i][j][x] = 1;
        }
        else{
            dp[i][j][x] = 0;
        }
    }
    else if (i == j - 1){
        int x1 = x + v[i];
        int x2 = x + v[j];
        if (x1 < k || x2 < k){
            dp[i][j][x] = 1;
        }
        else{
            dp[i][j][x] = 0;
        }
    }
    else{
        dp[i][j][x] = max(min(f(i + 1, j - 1, x + v[i], als + v[j]), f(i + 2, j, x + v[i], als + v[i + 1])),
                          min(f(i + 1, j - 1, x + v[j], als + v[i]), f(i, j - 2, x + v[j], als + v[j - 1])));
    }
    return dp[i][j][x];
}
int main(){
    cin>>n>>k;
    cin>>s;
    for (int i = 0; i < n; i++){
        if (s[i] == 'C'){
            v.push_back(1);
        }
        else{
            v.push_back(0);
        }
    }
    int ans = f(0, n - 1, 0, 0);
    if (ans == 1){
        cout<<"DA";
    }
    else{
        cout<<"NE";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 172340 KB Output is correct
2 Correct 152 ms 172308 KB Output is correct
3 Correct 151 ms 172328 KB Output is correct
4 Correct 154 ms 172552 KB Output is correct
5 Correct 154 ms 172396 KB Output is correct
6 Correct 121 ms 172492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 172340 KB Output is correct
2 Correct 152 ms 172308 KB Output is correct
3 Correct 151 ms 172328 KB Output is correct
4 Correct 154 ms 172552 KB Output is correct
5 Correct 154 ms 172396 KB Output is correct
6 Correct 121 ms 172492 KB Output is correct
7 Correct 150 ms 172372 KB Output is correct
8 Correct 129 ms 172312 KB Output is correct
9 Correct 129 ms 172360 KB Output is correct
10 Correct 153 ms 172532 KB Output is correct
11 Correct 127 ms 172420 KB Output is correct
12 Correct 151 ms 172432 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 172340 KB Output is correct
2 Correct 152 ms 172308 KB Output is correct
3 Correct 151 ms 172328 KB Output is correct
4 Correct 154 ms 172552 KB Output is correct
5 Correct 154 ms 172396 KB Output is correct
6 Correct 121 ms 172492 KB Output is correct
7 Correct 150 ms 172372 KB Output is correct
8 Correct 129 ms 172312 KB Output is correct
9 Correct 129 ms 172360 KB Output is correct
10 Correct 153 ms 172532 KB Output is correct
11 Correct 127 ms 172420 KB Output is correct
12 Correct 151 ms 172432 KB Output is correct
13 Correct 153 ms 172508 KB Output is correct
14 Correct 181 ms 172572 KB Output is correct
15 Correct 139 ms 172324 KB Output is correct
16 Correct 171 ms 172372 KB Output is correct
17 Correct 169 ms 172532 KB Output is correct
18 Correct 157 ms 172372 KB Output is correct