oj.uz

Submission #698635

# Submission time Handle Problem Language Result Execution time Memory
698635 2023-02-14T06:24:54 Z ld_minh4354 Kamenčići (COCI21_kamencici) C++14
30 / 70
 192 ms 524288 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][5],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 2260 KB Output is correct
3 Correct 2 ms 2248 KB Output is correct
4 Correct 1 ms 2260 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 2260 KB Output is correct
3 Correct 2 ms 2248 KB Output is correct
4 Correct 1 ms 2260 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 13524 KB Output is correct
8 Correct 5 ms 10828 KB Output is correct
9 Correct 6 ms 13524 KB Output is correct
10 Correct 4 ms 11348 KB Output is correct
11 Correct 5 ms 11348 KB Output is correct
12 Correct 6 ms 11860 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 2 ms 2248 KB Output is correct
4 Correct 1 ms 2260 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 13524 KB Output is correct
8 Correct 5 ms 10828 KB Output is correct
9 Correct 6 ms 13524 KB Output is correct
10 Correct 4 ms 11348 KB Output is correct
11 Correct 5 ms 11348 KB Output is correct
12 Correct 6 ms 11860 KB Output is correct
13 Runtime error 192 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -