oj.uz

Submission #988086

# Submission time Handle Problem Language Result Execution time Memory
988086 2024-05-24T04:26:03 Z 0pt1mus23 Kamenčići (COCI21_kamencici) C++14
0 / 70
 1 ms 348 KB 
#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[400][400];
string s;
int k;
int n;
int kafkef(int l,int r,int a,int b,bool flag=true){
    if(r<l || a==k || l==n || r==0){
        return 0;
    }
    if(b==k){
        return 1;
    }

    if(dp[l][r]!=-1){
        return dp[l][r];
    }
    
    int res =0;
    if(flag){
        res |= kafkef(l+1,r,a + (s[l]=='C'),b, !flag);
        res |= kafkef(l,r-1,a + (s[r]=='C'),b, !flag);
    }
    else{
        res= 1;
        res &= kafkef(l+1,r,a,b + (s[l]=='C'), !flag);
        res &= kafkef(l,r-1,a,b + (s[r]=='C'), !flag);
    }

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

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

    for(int i=0;i<n;i++){
        for(int j=n-1;j>=i;j--){
            dp[i][j]=-1;
        }
    }
    kafkef(0,n-1,0,0);
    // for(int i=0;i<n;i++){
    //     for(int j=n-1;j>=i;j--){
    //         if(dp[i][j]==1){
    //             cerr<<i<<" "<<j<<endl;
    //             drop("DA");
    //         }
    //     }
    // }
    if(dp[0][n-1]){
        drop("DA");
    }
    drop("NE");
}


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

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -