oj.uz

Submission #681755

# Submission time Handle Problem Language Result Execution time Memory
681755 2023-01-14T07:04:29 Z Iliya Kamenčići (COCI21_kamencici) C++17
70 / 70
 85 ms 183004 KB 
//Ye Rooz Khoob Miad ???
#include<bits/stdc++.h>
 
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
 
using namespace std;
typedef long long ll;
 
const int N = 350 + 10;
const int Inf = 1061109567;

int n, k, dp[N][N][N], ps[N];

bool solve(int l, int r, int m) {
	if(dp[l][r][m] != -1) 
		return dp[l][r][m];
	if(m >= k) 
		return dp[l][r][m] = 0;
	int h = ps[n] - m - (ps[r] - ps[l - 1]);
	if(h >= k) 
		return dp[l][r][m] = 1;
	return dp[l][r][m] = !(solve(l + 1, r, h)) | !(solve(l, r - 1, h));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	memset(dp, -1, sizeof dp);

	cin >> n >> k;
	string str;
	cin >> str;
	str = '!' + str;
	for(int i = 1; i <= n; i++)
		ps[i] = ps[i - 1] + (str[i] == 'C');
	cout << (solve(1, n, 0) ? "DA" : "NE") << '\n';
	
	return 0;
}

Compilation message

Main.cpp: In function 'bool solve(int, int, int)':
Main.cpp:22:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   22 |   return dp[l][r][m] = 0;
      |          ~~~~~~~~~~~~^~~
Main.cpp:25:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   25 |   return dp[l][r][m] = 1;
      |          ~~~~~~~~~~~~^~~
Main.cpp:26:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   26 |  return dp[l][r][m] = !(solve(l + 1, r, h)) | !(solve(l, r - 1, h));
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 182900 KB Output is correct
2 Correct 65 ms 182792 KB Output is correct
3 Correct 66 ms 182876 KB Output is correct
4 Correct 65 ms 182864 KB Output is correct
5 Correct 67 ms 182912 KB Output is correct
6 Correct 64 ms 182832 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 182900 KB Output is correct
2 Correct 65 ms 182792 KB Output is correct
3 Correct 66 ms 182876 KB Output is correct
4 Correct 65 ms 182864 KB Output is correct
5 Correct 67 ms 182912 KB Output is correct
6 Correct 64 ms 182832 KB Output is correct
7 Correct 64 ms 182852 KB Output is correct
8 Correct 65 ms 182920 KB Output is correct
9 Correct 64 ms 182860 KB Output is correct
10 Correct 64 ms 182820 KB Output is correct
11 Correct 65 ms 182816 KB Output is correct
12 Correct 66 ms 182896 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 182900 KB Output is correct
2 Correct 65 ms 182792 KB Output is correct
3 Correct 66 ms 182876 KB Output is correct
4 Correct 65 ms 182864 KB Output is correct
5 Correct 67 ms 182912 KB Output is correct
6 Correct 64 ms 182832 KB Output is correct
7 Correct 64 ms 182852 KB Output is correct
8 Correct 65 ms 182920 KB Output is correct
9 Correct 64 ms 182860 KB Output is correct
10 Correct 64 ms 182820 KB Output is correct
11 Correct 65 ms 182816 KB Output is correct
12 Correct 66 ms 182896 KB Output is correct
13 Correct 65 ms 182860 KB Output is correct
14 Correct 85 ms 183004 KB Output is correct
15 Correct 68 ms 182796 KB Output is correct
16 Correct 81 ms 182844 KB Output is correct
17 Correct 76 ms 182860 KB Output is correct
18 Correct 69 ms 182912 KB Output is correct