oj.uz

Submission #899666

# Submission time Handle Problem Language Result Execution time Memory
899666 2024-01-06T20:29:46 Z Karoot Kamenčići (COCI21_kamencici) C++17
0 / 70
 118 ms 368644 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-1]-pref[right]+(left == 0 ? 0 : pref[left-1])) - antun == k)return 1;

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

    if (player)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 = 0; i < n; i++){
        char c; cin >> c;
        s += c;
        pref[i] = (c == 'C');
        if (i != 0)pref[i] += pref[i-1];
    }
    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(0, n-1, 0, 1))cout << "DA" << endl;
    else cout << "NE" << endl;

    



    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 368644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 368644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 368644 KB Output isn't correct
2 Halted 0 ms 0 KB -