oj.uz

Submission #487760

# Submission time Handle Problem Language Result Execution time Memory
487760 2021-11-16T14:33:10 Z errorgorn Kamenčići (COCI21_kamencici) C++17
70 / 70
 82 ms 175616 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

mt19937 rng(123123);

int n,k;
string s;

int tot=0;
int pref[355];

int memo[355][355][355];

int dp(int i,int j,int k){
	if (memo[i][j][k]!=-1) return memo[i][j][k];
	if (k==::k) return memo[i][j][k]=1;
	
	int other=tot-(pref[j]-pref[i-1])-k;
	int res=dp(i+1,j,other+(s[i]=='C'))&dp(i,j-1,other+(s[j]=='C'));
	
	res=1^res;
	
	//cerr<<i<<" "<<j<<" "<<k<<endl;
	return memo[i][j][k]=res;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	cin>>s;
	
	s="$"+s;
	
	rep(x,1,n+1){
		pref[x]=pref[x-1]+(s[x]=='C');
	}
	tot=pref[n];
	
	memset(memo,-1,sizeof(memo));
	
	if (dp(1,n,0)) cout<<"DA"<<endl;
	else cout<<"NE"<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 175616 KB Output is correct
2 Correct 61 ms 175372 KB Output is correct
3 Correct 60 ms 175360 KB Output is correct
4 Correct 60 ms 175316 KB Output is correct
5 Correct 62 ms 175324 KB Output is correct
6 Correct 60 ms 175352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 175616 KB Output is correct
2 Correct 61 ms 175372 KB Output is correct
3 Correct 60 ms 175360 KB Output is correct
4 Correct 60 ms 175316 KB Output is correct
5 Correct 62 ms 175324 KB Output is correct
6 Correct 60 ms 175352 KB Output is correct
7 Correct 64 ms 175300 KB Output is correct
8 Correct 60 ms 175312 KB Output is correct
9 Correct 62 ms 175304 KB Output is correct
10 Correct 61 ms 175304 KB Output is correct
11 Correct 60 ms 175304 KB Output is correct
12 Correct 60 ms 175300 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 175616 KB Output is correct
2 Correct 61 ms 175372 KB Output is correct
3 Correct 60 ms 175360 KB Output is correct
4 Correct 60 ms 175316 KB Output is correct
5 Correct 62 ms 175324 KB Output is correct
6 Correct 60 ms 175352 KB Output is correct
7 Correct 64 ms 175300 KB Output is correct
8 Correct 60 ms 175312 KB Output is correct
9 Correct 62 ms 175304 KB Output is correct
10 Correct 61 ms 175304 KB Output is correct
11 Correct 60 ms 175304 KB Output is correct
12 Correct 60 ms 175300 KB Output is correct
13 Correct 63 ms 175348 KB Output is correct
14 Correct 82 ms 175424 KB Output is correct
15 Correct 66 ms 175420 KB Output is correct
16 Correct 76 ms 175340 KB Output is correct
17 Correct 68 ms 175436 KB Output is correct
18 Correct 64 ms 175324 KB Output is correct