제출 #1279647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279647		asedre	Kamenčići (COCI21_kamencici)	C++20	70 / 70	81 ms	170648 KiB

Main

// written by Asedre
#include <iostream>
#include <cmath>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <numeric>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <cstring>
#include <unordered_map>
#define pb push_back
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define ull unsigned long long
using namespace std;

const int maxv = 1e6 + 3, maxn = 1e6 + 12, LOG = 25;
const int inf = 1e9 + 5;
const int MOD = 1e9 + 7, MOD2 = 1338519349;
const double PI = 3.14159265359;
//prime nums: 9059, 5419, 3571
void teztez( ) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}/*
ll binpow(ll x, ll p, ll mod) {
    if (!p) return 1;
    if (p % 2) return (x % mod * binpow(x, p - 1, mod)) % mod;
    ll xx = binpow(x, p / 2, mod);
    return (xx % mod * xx % mod) % mod;
}
*/
ll binpow(ll x, ll p) {
    if (!p) return 1;
    if (p % 2) return (x % MOD * binpow(x, p - 1) % MOD) % MOD;
    ll xx = binpow(x, p / 2) % MOD;
    return (xx * xx) % MOD;
}
ll gcd(ll a,ll b) {
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return abs(a * b) / gcd(a, b);
}
int dp[352][352][352], pref[352], n, k;

bool rec(int l, int r, int sum) {
    if (dp[l][r][sum] != -1) return dp[l][r][sum];
    
    int left = pref[r] - pref[l - 1];
    int op = pref[n] - left - sum;
    if (sum >= k) dp[l][r][sum] = false;
    else if (op >= k) dp[l][r][sum] = true;
    else {
        if (!rec(l + 1, r, op) or !rec(l, r - 1, op)) dp[l][r][sum] = true;
        else dp[l][r][sum] = false;
    }
    
    return dp[l][r][sum];
}
void solve( ) {
    string s;
    cin >> n >> k >> s;
    s = "8" + s;
    
    for (int i = 1; i <= n; i ++) {
        pref[i] = pref[i - 1] + (s[i] == 'C');
    }
    for (int i = 0; i <= 350; i ++) {
        for (int j = 0; j <= 350; j ++) {
            for (int k = 0; k <= 350; k ++) dp[i][j][k] = -1;
        }
    }
    
    cout << ((rec(1, n, 0)) ? "DA\n" : "NE\n");
}
signed main( ) {
    teztez( );
    //freopen("angle2.in", "r", stdin); freopen("angle2.out", "w", stdout);
    int testcases = 1;
    //cin >> testcases;
    while (testcases--) {
        solve( );
    }
    return 0;
}

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