Submission #1184268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184268		constnode	Kamenčići (COCI21_kamencici)	C++20	70 / 70	204 ms	38620 KiB

Main

#include<bits/stdc++.h>

#define LOCAL
#ifdef LOCAL
    #define debug(x) cerr << #x << " = " << (x) << endl;
    #define debugVec(v) cerr << #v << " = "; for (auto &e : v) cerr << e << " "; cerr << endl;
    #define debugPair(p) cerr << #p << " = (" << p.first << ", " << p.second << ")" << endl;
#else
    #define debug(x)
    #define debugVec(v)
    #define debugPair(p)
#endif

#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>b;i--)
#define repi(i,a,b) for(ll i=a;i<=b;i++)
#define rrepi(i,a,b) for(ll i=a;i>=b;i--)
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define ull unsigned ll
#define vvll vector<vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define endl '\n'
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

#define no cout << "NO" << endl;
#define yes cout << "YES" << endl;
using namespace std;


int n ,k;
string s;
unordered_map<string, bool> memo;
bool f(int l , int r,int x , int y){
    if(l > r) return false;
    string mkey = to_string(l) + "x" + to_string(r) + "x" + to_string(x) + "x" + to_string(y);
    if (memo.find(mkey) != memo.end()) return memo[mkey];
    bool win = false;
    char value = s[l];
    if (value == 'P') {
        if (!f(l + 1, r, y, x))
            win = true;
    } else {
        if (x > 0 and !f(l + 1, r, y, x - 1))
            win = true;
    }
    if (!win) {
        value = s[r];
        if (value == 'P') {
            if (!f(l, r - 1, y, x))
                win = true;
        } else { 
            if (x > 0 && !f(l, r - 1, y, x - 1))
                win = true;
        }
    }
    
    memo[mkey] = win;
    return win;
}

void solve(){
    cin >> n >> k;
    cin >> s;
    bool ans = f(0 , n - 1, k - 1 , k - 1);
    cout << ((ans) ? "DA" : "NE") << endl;

    
    return;
}


/*
Base ? 
dp[i][0] = 


if L[i] == R[i]
dp[i][j] = max(dp[i][j] , dp[i-1][j-1])
else dp[i][j] = max(dp[i][j],max(dp[i-1][j] , dp[i][j - 1]))


*/
int main() {
    IO;
    int t;
    t = 1;
    //cin >> t;
    repi(i,1,t){
        //cout<<"Case "<<i<<": ";
        solve();
    }

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40