oj.uz

Submission #988080

# Submission time Handle Problem Language Result Execution time Memory
988080 2024-05-24T04:17:43 Z 0pt1mus23 Kamenčići (COCI21_kamencici) C++14
70 / 70
 131 ms 348760 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[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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 23008 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 4 ms 22872 KB Output is correct
5 Correct 4 ms 20984 KB Output is correct
6 Correct 3 ms 20960 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 23008 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 4 ms 22872 KB Output is correct
5 Correct 4 ms 20984 KB Output is correct
6 Correct 3 ms 20960 KB Output is correct
7 Correct 11 ms 46428 KB Output is correct
8 Correct 7 ms 45840 KB Output is correct
9 Correct 7 ms 46428 KB Output is correct
10 Correct 7 ms 45916 KB Output is correct
11 Correct 6 ms 45916 KB Output is correct
12 Correct 8 ms 45916 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 23008 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 4 ms 22872 KB Output is correct
5 Correct 4 ms 20984 KB Output is correct
6 Correct 3 ms 20960 KB Output is correct
7 Correct 11 ms 46428 KB Output is correct
8 Correct 7 ms 45840 KB Output is correct
9 Correct 7 ms 46428 KB Output is correct
10 Correct 7 ms 45916 KB Output is correct
11 Correct 6 ms 45916 KB Output is correct
12 Correct 8 ms 45916 KB Output is correct
13 Correct 131 ms 348760 KB Output is correct
14 Correct 127 ms 346884 KB Output is correct
15 Correct 114 ms 316224 KB Output is correct
16 Correct 131 ms 343380 KB Output is correct
17 Correct 125 ms 345424 KB Output is correct
18 Correct 124 ms 343380 KB Output is correct