oj.uz

Submission #1108633

# Submission time Handle Problem Language Result Execution time Memory
1108633 2024-11-04T17:00:35 Z Hora000 Kamenčići (COCI21_kamencici) C++17
70 / 70
 953 ms 68544 KB 
#include <bits/stdc++.h>
using namespace std;

map<array<array<int, 2>, 2>, int> dp; //1 ha az elso nyer, 0 ha elso veszt, -1 ha ismeretlen
int n, k;
string a;

bool h(int i, int j, array<int, 2> p, int s){ //intervallum i, j, p[0]je van az elsonek, p[1] van a masodiknak, sedik jatekos van
	array<int, 2> x = {i, j};
	array<array<int, 2>, 2> ind = {x, p};
	if(dp.count(ind) != 0) return dp[ind];
	if(p[0] >= k) return dp[ind] = 0; //elso veszt
	if(p[1] >= k) return dp[ind] = 1; //elso nyer
	
	array<int, 2> p2 = p;
	if(a[i] == 'C') p2[s]++;
	bool o1 = h(i + 1, j, p2, 1 - s);
	p2 = p;
	if(a[j] == 'C') p2[s]++;
	bool o2 = h(i, j - 1, p2, 1 - s);
	
	if(s == 0){
		if(o1 || o2) return dp[ind] = 1; //ha van nyer
		else return dp[ind] = 0;
	}
	if(!o1 || !o2) return dp[ind] = 0; //ha van veszto
	return dp[ind] = 1; //ha mindketto nyero az elsonek
}

int main() {
	cin >> n >> k;
	cin >> a;
	if(h(0, n - 1, {0, 0}, 0)) cout << "DA";
	else cout << "NE";
}

Compilation message

Main.cpp: In function 'bool h(int, int, std::array<int, 2>, int)':
Main.cpp:12:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   12 |  if(p[0] >= k) return dp[ind] = 0; //elso veszt
Main.cpp:13:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   13 |  if(p[1] >= k) return dp[ind] = 1; //elso nyer
Main.cpp:23:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   23 |   if(o1 || o2) return dp[ind] = 1; //ha van nyer
Main.cpp:24:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   24 |   else return dp[ind] = 0;
Main.cpp:26:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   26 |  if(!o1 || !o2) return dp[ind] = 0; //ha van veszto
Main.cpp:27:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |  return dp[ind] = 1; //ha mindketto nyero az elsonek

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 2 ms 600 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 1 ms 504 KB Output is correct
14 Correct 953 ms 68544 KB Output is correct
15 Correct 118 ms 11336 KB Output is correct
16 Correct 756 ms 54344 KB Output is correct
17 Correct 244 ms 22604 KB Output is correct
18 Correct 76 ms 8004 KB Output is correct