Submission #1108633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108633		Hora000	Kamenčići (COCI21_kamencici)	C++17	70 / 70	953 ms	68544 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40