Submission #1073051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073051		Gromp15	Homework (CEOI22_homework)	C++17	100 / 100	405 ms	254784 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
	string s; cin >> s;
	vector<int> type; // 0 = max, 1 = min, 2 = ?
	vector<int> lst;
	vector<ar<int, 2>> adj;
	int on = 0;
	for (int i = 0; i < sz(s); i++) {
		if (s[i] == '?') {
			adj.push_back({-1, -1});
			lst.emplace_back(on++);
			type.emplace_back(2);
		}
		else if (s[i] == ')') {
			assert(lst.size() > 2);
			int x = lst.back(); lst.pop_back();
			int y = lst.back(); lst.pop_back();
			int v = lst.back();
			adj[v] = {x, y};
		}
		else if (i+2 < sz(s)) {
			if (s.substr(i, 3) == "min") {
				lst.emplace_back(on++);
				type.push_back(1);
				adj.push_back({-1, -1});
				i += 2;
			}
			else if (s.substr(i, 3) == "max") {
				lst.emplace_back(on++);
				type.push_back(0);
				adj.push_back({-1, -1});
				i += 2;
			}
		}
	}
	vector<ar<ar<int, 2>, 3>> dp(on), dp2(on);
	auto dfs = [&](auto&& s, int v) -> void {
		for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++) dp[v][i][j] = -1e9, dp2[v][i][j] = 1e9;
		if (~adj[v][0]) {
			auto [l, r] = adj[v];
			s(s, l);
			s(s, r);
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					for (int k1 = 0; k1 < 2; k1++) for (int k2 = 0; k2 < 2; k2++) if (!k1 || !k2) {
						if (type[v] == 0) {
							ckmax(dp[v][max(i, j)][k1||k2], dp[l][i][k1] + dp[r][j][k2]);
							ckmin(dp2[v][max(i, j)][k1||k2], dp2[l][i][k1] + dp2[r][j][k2]);
						}
						else {
							assert(type[v] == 1);
							ckmax(dp[v][min(i, j)][k1||k2], dp[l][i][k1] + dp[r][j][k2]);
							ckmin(dp2[v][min(i, j)][k1||k2], dp2[l][i][k1] + dp2[r][j][k2]);
						}
					}
				}
			}
		}
		else {
			for (int i = 0; i < 3; i++) {
				dp[v][i][i==1] = !i, dp2[v][i][i==1] = !i;
			}
		}
	};
	dfs(dfs, 0);
	cout << dp[0][1][1] - dp2[0][1][1] + 1 << '\n';



}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

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