oj.uz

Submission #581680

# Submission time Handle Problem Language Result Execution time Memory
581680 2022-06-23T03:19:54 Z chirathnirodha Kamenčići (COCI21_kamencici) C++17
70 / 70
 161 ms 335992 KB 
//Coded by Chirath Nirodha
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
int n,k;
string s;
ll dp[350][350][350];
ll red[350];
void rec(int a,int b,int c){
	if(dp[a][b][c]!=-1)return;
	int x=red[n-1]-c-red[b];if(a>0)x+=red[a-1];
	if(c>=k){dp[a][b][c]=0;return;}
	if(x>=k){dp[a][b][c]=1;return;}
	if(a==b ){
		if(s[a]=='C' && c==k-1)dp[a][b][c]=0;
		else dp[a][b][c]=1;
	} 
	if(dp[a][b][c]!=-1)return;
	rec(a+1,b,x);rec(a,b-1,x);
	if(dp[a+1][b][x]==false || dp[a][b-1][x]==false)dp[a][b][c]=1;
	else dp[a][b][c]=0;
}
void solve(){
    io();
	cin>>n>>k;
	cin>>s;
	for(int i=0;i<n;i++){
		if(s[i]=='C')red[i]=1;
		else red[i]=0;
		if(i>0)red[i]+=red[i-1];
	}
	memset(dp,-1,sizeof(dp));
	rec(0,n-1,0);
	if(dp[0][n-1][0]==1)cout<<"DA"<<endl;
	else cout<<"NE"<<endl;
}
int main(){
    io();
	solve();
	//int t;cin>>t;for(int i=0;i<t;i++)solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 335820 KB Output is correct
2 Correct 142 ms 335808 KB Output is correct
3 Correct 121 ms 335872 KB Output is correct
4 Correct 131 ms 335824 KB Output is correct
5 Correct 122 ms 335828 KB Output is correct
6 Correct 121 ms 335820 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 335820 KB Output is correct
2 Correct 142 ms 335808 KB Output is correct
3 Correct 121 ms 335872 KB Output is correct
4 Correct 131 ms 335824 KB Output is correct
5 Correct 122 ms 335828 KB Output is correct
6 Correct 121 ms 335820 KB Output is correct
7 Correct 123 ms 335956 KB Output is correct
8 Correct 119 ms 335916 KB Output is correct
9 Correct 129 ms 335928 KB Output is correct
10 Correct 124 ms 335828 KB Output is correct
11 Correct 119 ms 335904 KB Output is correct
12 Correct 121 ms 335804 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 335820 KB Output is correct
2 Correct 142 ms 335808 KB Output is correct
3 Correct 121 ms 335872 KB Output is correct
4 Correct 131 ms 335824 KB Output is correct
5 Correct 122 ms 335828 KB Output is correct
6 Correct 121 ms 335820 KB Output is correct
7 Correct 123 ms 335956 KB Output is correct
8 Correct 119 ms 335916 KB Output is correct
9 Correct 129 ms 335928 KB Output is correct
10 Correct 124 ms 335828 KB Output is correct
11 Correct 119 ms 335904 KB Output is correct
12 Correct 121 ms 335804 KB Output is correct
13 Correct 125 ms 335884 KB Output is correct
14 Correct 161 ms 335948 KB Output is correct
15 Correct 126 ms 335908 KB Output is correct
16 Correct 145 ms 335992 KB Output is correct
17 Correct 147 ms 335948 KB Output is correct
18 Correct 130 ms 335840 KB Output is correct