Submission #943584

#	Time	Username	Problem	Language	Result	Execution time	Memory
943584		MinaRagy06	Homework (CEOI22_homework)	C++17	100 / 100	143 ms	167892 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int md[10'000'005];
string s;
array<int, 3> solve(int l, int r) {
	if (l == r && s[l] == '?') {
		return {0, 0, 1};
	}
	array<int, 3> vl = solve(l + 4, md[l] - 1), vr = solve(md[l] + 1, r - 1);
	array<int, 3> v = {0, 0, 0};
	v[2] = vl[2] + vr[2];
	if (s[l + 1] == 'a') {
		//max
		v[1] = v[2] - min(vl[2] - vl[1], vr[2] - vr[1]);
		v[0] = vl[0] + vr[0] + 1;
	} else {
		//min
		v[0] = min(vl[0], vr[0]);
		v[1] = v[2] - (vl[2] - vl[1] + vr[2] - vr[1]);
	}
// 	cout << s.substr(l, r - l + 1) << ": " << v[0] << ' ' << v[1] << '\n';
	return v;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> s;
	vector<int> v;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'm') {
			v.push_back(i);
		} else if (s[i] == ',') {
			md[v.back()] = i;
		} else if (s[i] == ')') {
			v.pop_back();
		}
	}
	array<int, 3> x = solve(0, s.size() - 1);
	cout << x[1] - x[0] + 1 << '\n';
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34