oj.uz

Submission #698636

# Submission time Handle Problem Language Result Execution time Memory
698636 2023-02-14T06:25:39 Z ld_minh4354 Kamenčići (COCI21_kamencici) C++14
70 / 70
 253 ms 515188 KB 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back

int n,k,dpsave[355][355][355][3],a[355],lc[355],rc[355];

int dp(int l,int r,int c,int t)
{
	if (dpsave[l][r][c][t]!=-1) return dpsave[l][r][c][t];
	if (c>=k)
	{
		dpsave[l][r][c][t]=0;
//		cout<<l<<" "<<r<<" "<<c<<" "<<t<<" "<<"0a"<<"\n";
		return 0;
	}
	if (lc[l]+rc[r]-c>=k)
	{
		dpsave[l][r][c][t]=1;
//		cout<<l<<" "<<r<<" "<<c<<" "<<t<<" "<<"1a"<<"\n";
		return 1;
	}
	
	int ans;
	if (t==0) ans=max(dp(l+1, r, c + a[l+1], 1-t), dp(l, r+1, c + a[n-r], 1-t));
	else 	  ans=min(dp(l+1, r, c         , 1-t), dp(l, r+1, c         , 1-t));
	
	dpsave[l][r][c][t]=ans;
//	cout<<l<<" "<<r<<" "<<c<<" "<<t<<" "<<ans<<"\n";
	return ans;
}

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	string s;
	int i,j,w;
	
	cin>>n>>k>>s;
	for (i=1;i<n+1;i++) if (s[i-1]=='C') a[i]=1;else a[i]=0;
	
	lc[0]=0;
	for (i=1;i<n+1;i++) lc[i]=lc[i-1]+a[i];
	
	rc[0]=0;
	for (i=1;i<n+1;i++) rc[i]=rc[i-1]+a[n+1-i];
	
	for (i=0;i<n+1;i++) for (j=0;j<n+1;j++) for (w=0;w<n+1;w++) dpsave[i][j][w][0]=dpsave[i][j][w][1]=-1;
	
	if (dp(0,0,0,0)==1) cout<<"DA";else cout<<"NE";
//	cout<<dpsave[0][0][0][0];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 2116 KB Output is correct
3 Correct 1 ms 2132 KB Output is correct
4 Correct 1 ms 2116 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 2116 KB Output is correct
3 Correct 1 ms 2132 KB Output is correct
4 Correct 1 ms 2116 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 5 ms 11220 KB Output is correct
8 Correct 4 ms 9172 KB Output is correct
9 Correct 5 ms 11220 KB Output is correct
10 Correct 4 ms 9556 KB Output is correct
11 Correct 4 ms 9556 KB Output is correct
12 Correct 6 ms 10068 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 2116 KB Output is correct
3 Correct 1 ms 2132 KB Output is correct
4 Correct 1 ms 2116 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 5 ms 11220 KB Output is correct
8 Correct 4 ms 9172 KB Output is correct
9 Correct 5 ms 11220 KB Output is correct
10 Correct 4 ms 9556 KB Output is correct
11 Correct 4 ms 9556 KB Output is correct
12 Correct 6 ms 10068 KB Output is correct
13 Correct 210 ms 515188 KB Output is correct
14 Correct 238 ms 512344 KB Output is correct
15 Correct 183 ms 463768 KB Output is correct
16 Correct 253 ms 506512 KB Output is correct
17 Correct 219 ms 509512 KB Output is correct
18 Correct 206 ms 506448 KB Output is correct