oj.uz

Submission #899668

# Submission time Handle Problem Language Result Execution time Memory
899668 2024-01-06T20:37:21 Z Karoot Kamenčići (COCI21_kamencici) C++17
70 / 70
 133 ms 368980 KB 
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

const int MAXN = 361;
int mem[MAXN][MAXN][MAXN][2];
int pref[MAXN];
int n, k;
string s = ".";

int dp(int left, int right, int antun, int player){
    if (antun >= k) return 0;
    if (pref[n]-pref[right]+pref[left-1]-antun >= k)return 1;

    if (mem[left][right][antun][player] != -1)return mem[left][right][antun][player];

    if (player)return mem[left][right][antun][player] = max(dp(left+1, right, antun+(s[left] == 'C'), 0), dp(left, right-1, antun+(s[right] == 'C'), 0));
    
    return mem[left][right][antun][player] = min(dp(left+1, right, antun, 1), dp(left, right-1, antun, 1));   
}

int main(){
    scoobydoobydoo();
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        char c; cin >> c;
        s += c;
        pref[i] = pref[i-1]+(c == 'C');
    }
    for (int i = 0; i <= 360; i++){
        for (int j = 0; j <= 360; j++){
            for (int k = 0; k <= 360; k++){
                mem[i][j][k][0] = -1;
                mem[i][j][k][1] = -1;
            }
        }
    }
    
    
    if (dp(1, n, 0, 1))cout << "DA" << endl;
    else cout << "NE" << endl;

    



    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 368600 KB Output is correct
2 Correct 88 ms 368464 KB Output is correct
3 Correct 84 ms 368456 KB Output is correct
4 Correct 86 ms 368468 KB Output is correct
5 Correct 83 ms 368692 KB Output is correct
6 Correct 83 ms 368468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 368600 KB Output is correct
2 Correct 88 ms 368464 KB Output is correct
3 Correct 84 ms 368456 KB Output is correct
4 Correct 86 ms 368468 KB Output is correct
5 Correct 83 ms 368692 KB Output is correct
6 Correct 83 ms 368468 KB Output is correct
7 Correct 84 ms 368468 KB Output is correct
8 Correct 84 ms 368520 KB Output is correct
9 Correct 82 ms 368696 KB Output is correct
10 Correct 76 ms 368560 KB Output is correct
11 Correct 78 ms 368484 KB Output is correct
12 Correct 75 ms 368468 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 368600 KB Output is correct
2 Correct 88 ms 368464 KB Output is correct
3 Correct 84 ms 368456 KB Output is correct
4 Correct 86 ms 368468 KB Output is correct
5 Correct 83 ms 368692 KB Output is correct
6 Correct 83 ms 368468 KB Output is correct
7 Correct 84 ms 368468 KB Output is correct
8 Correct 84 ms 368520 KB Output is correct
9 Correct 82 ms 368696 KB Output is correct
10 Correct 76 ms 368560 KB Output is correct
11 Correct 78 ms 368484 KB Output is correct
12 Correct 75 ms 368468 KB Output is correct
13 Correct 79 ms 368692 KB Output is correct
14 Correct 97 ms 368576 KB Output is correct
15 Correct 80 ms 368468 KB Output is correct
16 Correct 93 ms 368468 KB Output is correct
17 Correct 101 ms 368980 KB Output is correct
18 Correct 78 ms 368712 KB Output is correct