Submission #1187293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187293		Mirbala	Kamenčići (COCI21_kamencici)	C++20	30 / 70	39 ms	44612 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mir signed
#define pii pair<int, int>
#define tup tuple<int, int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define bs << ' '
#define bss << ' ' <<
#define endl \
    << '\n'
#define each(i, x) for (auto &i : x)
#define say(x) cout << x endl;
#define fastt                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define itn int
const int inf = 1e9;
const long long inff = 2e18;
const int mod = 1e18;
vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};

void maxx(int &a, int b)
{
    a = max(a, b);
}
void minn(int &a, int b)
{
    a = min(a, b);
}

int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

int cel(int a, int b)
{
    return (a - 1) / b + 1;
}

int binpow(int a, int b)
{
    if (!b)
        return 1;
    int res = binpow(a % mod, b / 2);
    res = (res * res) % mod;
    if (b & 1)
        res = (res * (a % mod)) % mod;
    return res;
}

const int sq = 100000;

string xorr(string a, string b)
{
    if (a.size() < b.size())
        swap(a, b);
    int j = b.size() - 1;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        if (j < 0)
            break;
        a[i] = char((a[i] - '0') ^ (b[j] - '0') + '0');
        j--;
    }
    return a;
}

// int vur(int a, int b){
//     return (((a * b) % mod) + mod) % mod;
// }


struct Node
{
    int l, r;
    unsigned long long lazy, sum;
    Node *L = nullptr, *R = nullptr;
    Node(int ll, int rr)
    {
        l = ll;
        r = rr;
        lazy = sum = 0;
    }
    void ext()
    {
        if (lazy && l != r)
        {
            int mid = (l + r) / 2;
            if (!L)
                L = new Node(l, mid);
            if (!R)
                R = new Node(mid + 1, r);
            L->lazy += lazy;
            R->lazy += lazy;
            L->sum += lazy * (mid - l + 1);
            R->sum += lazy * (r - mid);
        }
        lazy = 0;
    }
    void add(int lf, int rf, int k)
    {
        if (l >= lf && rf >= r)
        {
            lazy += k;
            sum += (r - l + 1) * k;
            return;
        }
        if (l > rf || r < lf)
            return;
        ext();
        int mid = (l + r) >> 1;
        if (!L && !(mid < lf || l > rf))
            L = new Node(l, mid);
        if (!R && !(r < lf || mid + 1 > rf))
            R = new Node(mid + 1, r);
        if (!(mid < lf || l > rf))
            L->add(lf, rf, k);
        if (!(r < lf || mid + 1 > rf))
            R->add(lf, rf, k);
        sum = (L ? L->sum : 0) + (R ? R->sum : 0);
    }
    unsigned long long query(int lf, int rf)
    {
        if (lf > r || rf < l)
            return 0;
        if (l >= lf && rf >= r)
            return sum;
        int mid = (l + r) >> 1;
        ext();
        return (L && !(mid < lf || l > rf) ? L->query(lf, rf) : 0) + (R && !(r < lf || mid + 1 > rf) ? R->query(lf, rf) : 0);
    }
};


//
const int sz = 355;
bool dp[355][355][355];
bool vis[355][355][355];
string s;
int k;
bool dfs(int l,int r,int biz,int req){
    if(biz > k)return 0;
    if(req > k)return 1; 
    if(vis[l][r][biz])return dp[l][r][biz];
    vis[l][r][biz] = 1;
    bool sol = dfs(l+1,r,req,biz + (s[l] == 'C')),sag = dfs(l,r-1,req,biz + (s[r] == 'C'));
    sol ^= 1;
    sag ^= 1;
    return dp[l][r][biz] = (sol | sag);
}
void solve()
{
    int n;
    cin >> n >> k;
    cin >> s;
    s = '.' + s;
    if(dfs(1,n,0,0))say("DA")
    else say("NE")
    
}

mir main()
{
    fastt int t = 1;
    // cin >> t;
    for (int tt = 1; tt <= t; ++tt)
    {
        // cout << "Case " << tt << ": ";
        solve();
    }
    // int n;
    // while(cin >> n){
    //     solve(n);
    // }
    return 0;
}

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