Submission #988080

#	Time	Username	Problem	Language	Result	Execution time	Memory
988080		0pt1mus23	Kamenčići (COCI21_kamencici)	C++14	70 / 70	131 ms	348760 KiB

Main

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define ins insert
#define pb push_back
#define int long long
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl;return;
#define reach cerr << "reached >.<!" << endl;
/*
    m : 11059739 -> l ~23
    p : 4567896467
*/
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7, sze = 1e6 + 50, inf = LLONG_MAX, prime = 2333;

//\\
dp / binary search / greedy / sprase table / segment tree 
//

int dp[360][360][360];
string s;
int k;
int n;
int p[sze];
int q(int l,int r,int a){
    int c = 0;
    if(l!=0){
        c = p[l-1];
    }
    return p[n-1] - a - (p[r] - c);
}
int kafkef(int l,int r,int a){
    if(dp[l][r][a]!=-1){
        return dp[l][r][a];
    }
    if(a>=k){
        return 0;
    }
    int b = q(l,r,a);
    if(b>=k){
        return 1;
    }
    if(l>=r){
        return 0;
    }


    int res=0;
    
    if(kafkef(l+2,r,a + (s[l]=='C')) && kafkef(l+1,r-1,a + (s[l]=='C'))){
        res = 1;
    }

    if(kafkef(l,r-2,a + (s[r]=='C')) && kafkef(l+1,r-1,a + (s[r]=='C'))){
        res =1;
    }

    // cout<<l<<" "<<r<<" "<<a<<" "<<b<<" "<<res<<endl;
    return dp[l][r][a]=res;
}

void gkd(){
    cin>>n>>k;
    cin>>s;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int x=0;x<k;x++){
                dp[i][j][x]=-1;
            }
        }
    }
    for(int i=0;i<n;i++){
        p[i]=(s[i]=='C');
        if(i){
            p[i]+=p[i-1];
        }
    }
    if(kafkef(0,n-1,0)){
        drop("DA");
    }
    drop("NE");
}


signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1; //cin>>tt;
    while (tt--)gkd();
}

Compilation message (stderr)

Main.cpp:19:1: warning: multi-line comment [-Wcomment]
   19 | //\\
      | ^

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