Submission #1184248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184248		constnode	Kamenčići (COCI21_kamencici)	C++20	0 / 70	0 ms	324 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;


void solve(){
    int n ,k;
    cin >> n >> k;
    string s;
    cin >> s;
    int L = (n + 1) / 2;
    int R = n - L;
    vi A(L);
    vi B(R);
    rep(i , 0 , L){
        A[i] = (s[i] == 'C');
    }
    rep(i , 0 , R){
        B[i] = (s[n - 1 - i] == 'C');
    }
    //INF de yoxla.
    vector<vi>dp(L + 1 , vi(R + 1 , 0));
    dp[L][R] = 0;
    rrepi(i,L,0){
        rrepi(j , R , 0){
            if(i == L and j == R) {continue;}//pass
            else{
                if((i + j) % 2 == 0){
                    int res = k;
                    if(i != L){
                        int c =((A[i] != 1) ? ( dp[i + 1][j] + A[i]) : k);
                        res = min(res , c);
                    }
                    if(j != R){
                        int c =((B[j] != 1) ? ( dp[i][j + 1] + B[j]) : k);
                        res = min(res , c);
                    }
                    dp[i][j] = res;
                }
                else{
                    int res = -1;
                    if(i != L){
                        int c = (A[i] == 1) ? 0 : dp[i + 1][j];
                        res = max(res , c);
                    }
                    if(j != R){
                        int c = (B[j] == 1) ? 0 : dp[i][j + 1];
                        res = max(res ,c);
                    }
                    dp[i][j] = res;
                }

            }
        }
        
    }
    cout << ((dp[0][0] < k) ? "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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40