Submission #899668

#	Time	Username	Problem	Language	Result	Execution time	Memory
899668		Karoot	Kamenčići (COCI21_kamencici)	C++17	70 / 70	133 ms	368980 KiB

Main

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40