oj.uz

Submission #658373

# Submission time Handle Problem Language Result Execution time Memory
658373 2022-11-13T03:36:57 Z sam571128 Kamenčići (COCI21_kamencici) C++17
70 / 70
 55 ms 86696 KB 
#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

const int N = 355;
int dp[N][N][N], pref[N];

signed main(){
	fastio
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;

	int sum = 0;

	s = "$" + s;

	for(int i = 1; i <= n; i++){
		pref[i] = pref[i-1] + (s[i]=='C');
		sum += (s[i]=='C');
	}

	for(int l = n; l >= 1; l--){
		for(int r = l+1; r <= n; r++){
			for(int x = 0; x <= n; x++){
				int y = sum-(pref[r]-pref[l-1])-x;
				if(x >= k) dp[l][r][x] = false;
				else if(y >= k) dp[l][r][x] = true;
				else dp[l][r][x] = (!dp[l+1][r][y] || !dp[l][r-1][y]);
			}
		}
	}

	cout << (dp[1][n][0] ? "DA" : "NE") << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 580 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 580 KB Output is correct
7 Correct 2 ms 2132 KB Output is correct
8 Correct 1 ms 1860 KB Output is correct
9 Correct 1 ms 2132 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 1 ms 2004 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 580 KB Output is correct
7 Correct 2 ms 2132 KB Output is correct
8 Correct 1 ms 1860 KB Output is correct
9 Correct 1 ms 2132 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 1 ms 2004 KB Output is correct
13 Correct 46 ms 86696 KB Output is correct
14 Correct 51 ms 86168 KB Output is correct
15 Correct 38 ms 78108 KB Output is correct
16 Correct 45 ms 85148 KB Output is correct
17 Correct 55 ms 85692 KB Output is correct
18 Correct 45 ms 85196 KB Output is correct