oj.uz

Submission #887811

# Submission time Handle Problem Language Result Execution time Memory
887811 2023-12-15T09:06:31 Z Mr_Ph Kamenčići (COCI21_kamencici) C++17
70 / 70
 121 ms 338956 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<x, null_type,
ll mod=(ll)1e9+7;
ll mod1=998244353;
///the defines :)
#define endl '\n'
#define vi vector<int>
#define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i];
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
#define int long long
int dp[351][351][351];
vi arr;
int prf[351];
string s;
int k;
    int n;
int ans(int l,int r,int red)
{
    int turn=((l)+(n-r-1))&1;
    int red1=prf[n-1]-prf[r];
    red1+=(l?prf[l-1]:0);
    red1-=red;
    if((turn&&red==k)||(!turn&&red1==k))
        return turn;
    if(dp[l][r][red]!=-1)return dp[l][r][red];
    int e=0;
    if(turn)
    {
        e|=ans(l+1,r,red);
        e|=ans(l,r-1,red);
    }
    else
    {
        e=1;
        e&=ans(l+1,r,red+(s[l]=='C'));
        e&=ans(l,r-1,red+(s[r]=='C'));
    }
    return dp[l][r][red]=e;
}
void preprocess() {}
void solve()
{
    memset(dp,-1,sizeof dp);
    cin>>n>>k;
    cin>>s;
    prf[0]=s[0]=='C';
    for(int i=1;i<n;i++)
        prf[i]=prf[i-1]+(s[i]=='C');
    if(ans(0,n-1,0)!=0)cout<<"NE"<<endl;
    else cout<<"DA"<<endl;
}
signed main()
{
    // freopen("meta_game_input.txt","r",stdin);
    // freopen("otput.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    preprocess();
    int t=1,st;
    //cin>>t;
    while(t--)
        solve();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:67:13: warning: unused variable 'st' [-Wunused-variable]
   67 |     int t=1,st;
      |             ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 338832 KB Output is correct
2 Correct 45 ms 338892 KB Output is correct
3 Correct 40 ms 338772 KB Output is correct
4 Correct 40 ms 338840 KB Output is correct
5 Correct 41 ms 338768 KB Output is correct
6 Correct 40 ms 338704 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 338832 KB Output is correct
2 Correct 45 ms 338892 KB Output is correct
3 Correct 40 ms 338772 KB Output is correct
4 Correct 40 ms 338840 KB Output is correct
5 Correct 41 ms 338768 KB Output is correct
6 Correct 40 ms 338704 KB Output is correct
7 Correct 42 ms 338956 KB Output is correct
8 Correct 40 ms 338768 KB Output is correct
9 Correct 55 ms 338772 KB Output is correct
10 Correct 42 ms 338772 KB Output is correct
11 Correct 43 ms 338772 KB Output is correct
12 Correct 40 ms 338716 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 338832 KB Output is correct
2 Correct 45 ms 338892 KB Output is correct
3 Correct 40 ms 338772 KB Output is correct
4 Correct 40 ms 338840 KB Output is correct
5 Correct 41 ms 338768 KB Output is correct
6 Correct 40 ms 338704 KB Output is correct
7 Correct 42 ms 338956 KB Output is correct
8 Correct 40 ms 338768 KB Output is correct
9 Correct 55 ms 338772 KB Output is correct
10 Correct 42 ms 338772 KB Output is correct
11 Correct 43 ms 338772 KB Output is correct
12 Correct 40 ms 338716 KB Output is correct
13 Correct 39 ms 338904 KB Output is correct
14 Correct 58 ms 338928 KB Output is correct
15 Correct 42 ms 338868 KB Output is correct
16 Correct 63 ms 338940 KB Output is correct
17 Correct 53 ms 338772 KB Output is correct
18 Correct 43 ms 338884 KB Output is correct