oj.uz

Submission #861734

# Submission time Handle Problem Language Result Execution time Memory
861734 2023-10-16T21:00:12 Z Ahmed_Solyman Kamenčići (COCI21_kamencici) C++14
70 / 70
 64 ms 250964 KB 
/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_cxx;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("-O1")
//-------------------------------------------------------------//
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI acos(-1)
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sum_to(n) (n*(n+1))/2
#define pb push_back
#define pf push_front
#define fil(arr,x) memset(arr,x,sizeof(arr))
const ll mod=1e9+7;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,1,-1,-1,1};
//-------------------------------------------------------------//
ll lcm(ll a,ll b)
{
    return (max(a,b)/__gcd(a,b))*min(a,b);
}
void person_bool(bool x)
{
    cout<<(x?"DA":"NE")<<endl;
}
const int N=400;
int dp[N][N][N];
int n,k,ps[N],ss[N];
string s;
bool solve(int i,int j,int cnt){
	if(cnt>=k){
		return 0;
	}
	if(ps[i]+ss[j]-cnt>=k){
		return 1;
	}
	int &ret=dp[i][j][cnt];
	if(~ret)return ret;
	int turn=((i+j)%2)==((n-1)%2);
	if(turn==1){
		return ret=(solve(i+1,j,cnt+(s[i]=='C'))|solve(i,j-1,cnt+(s[j]=='C')));
	}
	else{
		return ret=!(((!solve(i+1,j,cnt))|(!solve(i,j-1,cnt))));
	}
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #ifndef ONLINE_JUDGE
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    #endif
    fast
    fil(dp,-1);
    cin>>n>>k>>s;
    for(int i=1;i<n;i++)ps[i]=ps[i-1]+(s[i-1]=='C');
    for(int i=n-2;i;i--)ss[i]=ss[i+1]+(s[i+1]=='C');
    person_bool(solve(0,n-1,0));
    return 0;
}

Compilation message

Main.cpp: In function 'bool solve(int, int, int)':
Main.cpp:53:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   53 |   return ret=(solve(i+1,j,cnt+(s[i]=='C'))|solve(i,j-1,cnt+(s[j]=='C')));
      |          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:56:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   56 |   return ret=!(((!solve(i+1,j,cnt))|(!solve(i,j-1,cnt))));
      |          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 250704 KB Output is correct
2 Correct 43 ms 250812 KB Output is correct
3 Correct 43 ms 250708 KB Output is correct
4 Correct 46 ms 250964 KB Output is correct
5 Correct 43 ms 250920 KB Output is correct
6 Correct 44 ms 250708 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 250704 KB Output is correct
2 Correct 43 ms 250812 KB Output is correct
3 Correct 43 ms 250708 KB Output is correct
4 Correct 46 ms 250964 KB Output is correct
5 Correct 43 ms 250920 KB Output is correct
6 Correct 44 ms 250708 KB Output is correct
7 Correct 44 ms 250864 KB Output is correct
8 Correct 43 ms 250704 KB Output is correct
9 Correct 43 ms 250792 KB Output is correct
10 Correct 46 ms 250716 KB Output is correct
11 Correct 45 ms 250704 KB Output is correct
12 Correct 44 ms 250784 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 250704 KB Output is correct
2 Correct 43 ms 250812 KB Output is correct
3 Correct 43 ms 250708 KB Output is correct
4 Correct 46 ms 250964 KB Output is correct
5 Correct 43 ms 250920 KB Output is correct
6 Correct 44 ms 250708 KB Output is correct
7 Correct 44 ms 250864 KB Output is correct
8 Correct 43 ms 250704 KB Output is correct
9 Correct 43 ms 250792 KB Output is correct
10 Correct 46 ms 250716 KB Output is correct
11 Correct 45 ms 250704 KB Output is correct
12 Correct 44 ms 250784 KB Output is correct
13 Correct 43 ms 250960 KB Output is correct
14 Correct 64 ms 250708 KB Output is correct
15 Correct 31 ms 250716 KB Output is correct
16 Correct 48 ms 250936 KB Output is correct
17 Correct 37 ms 250716 KB Output is correct
18 Correct 31 ms 250712 KB Output is correct