A - Problem Entries

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

int main() {
	freopen("problem.in", "r", stdin);
	freopen("problem.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	int time[605], value[605];
	for (int i = 1; i <= m; i++) {
		cin >> time[i] >> value[i];
	}
	int dp[605][605] = {0};
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (j >= time[i]) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time[i]] + value[i]);
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[m][n] << endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

B - Trivial Script Interpretation

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

struct Var {
	string type;
	unsigned int int_val;
	string str_val;
	unsigned char char_val;
};

map<string, Var> vars;

void process_instruction(const string& line) {
	stringstream ss(line);
	string cmd;
	ss >> cmd;
	if (cmd == "string" || cmd == "int" || cmd == "char") {
		string var_name, val;
		ss >> var_name;
		if (cmd == "string") {
			ss >> val;
			Var v;
			v.type = "string";
			v.str_val = val;
			vars[var_name] = v;
		} else if (cmd == "int") {
			unsigned int x;
			ss >> x;
			Var v;
			v.type = "int";
			v.int_val = x;
			vars[var_name] = v;
		} else if (cmd == "char") {
			char c;
			ss >> c;
			Var v;
			v.type = "char";
			v.char_val = (unsigned char)c;
			vars[var_name] = v;
		}
	} else if (cmd == "set") {
		string var_name, op, val;
		ss >> var_name >> op;
		if (op == "value") {
			Var& v = vars[var_name];
			if (v.type == "string") {
				ss >> val;
				v.str_val = val;
			} else if (v.type == "int") {
				unsigned int x;
				ss >> x;
				v.int_val = x;
			} else if (v.type == "char") {
				char c;
				ss >> c;
				v.char_val = (unsigned char)c;
			}
		} else if (op == "variable") {
			string other_var;
			ss >> other_var;
			Var& v = vars[var_name];
			Var& other = vars[other_var];
			if (v.type == "string") {
				v.str_val = other.str_val;
			} else if (v.type == "int") {
				v.int_val = other.int_val;
			} else if (v.type == "char") {
				v.char_val = other.char_val;
			}
		}
	} else if (cmd == "output") {
		string op, val;
		ss >> op;
		if (op == "value") {
			string rest;
			getline(ss, rest);
			size_t start = rest.find_first_not_of(' ');
			if (start != string::npos) {
				rest = rest.substr(start);
			}
			cout << rest << endl;
		} else if (op == "variable") {
			string var_name;
			ss >> var_name;
			Var& v = vars[var_name];
			if (v.type == "string") {
				cout << v.str_val << endl;
			} else if (v.type == "int") {
				cout << (int)v.int_val << endl;
			} else if (v.type == "char") {
				cout << "[ASCII " << (int) ((int8_t) v.char_val) << "]" << endl;
			}
		}
	} else if (cmd == "add") {
		string var_name, op;
		ss >> var_name >> op;
		Var& v = vars[var_name];
		if (op == "value") {
			if (v.type == "string") {
				string val;
				ss >> val;
				v.str_val += val;
			} else if (v.type == "int") {
				unsigned int x;
				ss >> x;
				v.int_val += x;
			} else if (v.type == "char") {
				int x;
				ss >> x;
				v.char_val = (unsigned char)((unsigned int)v.char_val + x);
			}
		} else if (op == "variable") {
			string other_var;
			ss >> other_var;
			Var& other = vars[other_var];
			if (v.type == "string") {
				v.str_val += other.str_val;
			} else if (v.type == "int") {
				v.int_val += other.int_val;
			}
		}
	} else if (cmd == "minus") {
		string var_name, op;
		ss >> var_name >> op;
		Var& v = vars[var_name];
		if (op == "value") {
			if (v.type == "int") {
				unsigned int x;
				ss >> x;
				v.int_val -= x;
			} else if (v.type == "char") {
				int x;
				ss >> x;
				v.char_val = (unsigned char)((unsigned int)v.char_val - x);
			}
		} else if (op == "variable") {
			string other_var;
			ss >> other_var;
			Var& other = vars[other_var];
			if (v.type == "int") {
				v.int_val -= other.int_val;
			}
		}
	} else if (cmd == "for") {
		int times;
		ss >> times;
		string rest;
		getline(ss, rest);
		size_t start = rest.find_first_not_of(' ');
		if (start != string::npos) {
			rest = rest.substr(start);
		}
		for (int i = 0; i < times; ++i) {
			process_instruction(rest);
		}
	}
}

int main() {
	freopen("interpretation.in", "r", stdin);
	freopen("interpretation.out", "w", stdout);
	int n;
	cin >> n;
	cin.ignore();
	for (int i = 0; i < n; ++i) {
		string line;
		getline(cin, line);
		process_instruction(line);
	}
	return 0;
}

C - Signal Traversal

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

struct NodeState {
	int index;
	int length;
	int signal;
};

int cs(int type, int signal) {
	if (type == 0) return 0;
	if (type == 2) return 15;
	if (type == 3) return signal - 1;
	if (type >= 4 && type <= 7) {
		int boost = 0;
		if (type == 4) boost = 0;
		else if (type == 5) boost = 1;
		else if (type == 6) boost = 2;
		else if (type == 7) boost = 4;
		return (signal + boost) - 1;
	}
	return signal;
}

int dfs(const vector<int>& tree) {
	if (tree.empty() || tree[0] != 1) {
		return 0;
	}
	int max_l = 0;
	stack<NodeState> stk;
	stk.push({0, 0, 15});
	while (!stk.empty()) {
		NodeState c = stk.top();
		stk.pop();
		if (c.index >= tree.size() || c.signal <= 0 || tree[c.index] == 0) {
			continue;
		}
		int new_s = cs(tree[c.index], c.signal);
		int new_l = c.length + 1;
		if (new_l > max_l) {
			max_l = new_l;
		}
		if (new_s > 0) {
			stk.push({2 * c.index + 2, new_l, new_s});
			stk.push({2 * c.index + 1, new_l, new_s});
		}
	}
	return max_l;
}

int main() {
	freopen("traversal.in", "r", stdin);
	freopen("traversal.out", "w", stdout);
	int n;
	cin >> n;
	vector<int> tree(n);
	for (int i = 0; i < n; i++) {
		cin >> tree[i];
	}
	int result = dfs(tree);
	cout << result << endl;
	return 0;
}

D - Population

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

int main() {
	freopen("population.in", "r", stdin);
	freopen("population.out", "w", stdout);
	int m, n;
	long long steps;
	cin >> m >> n >> steps;
	vector<vector<int> > grid(m, vector<int>(n));
	vector<vector<int> > fixed(m, vector<int>(n));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> grid[i][j];
			if (grid[i][j] >= 2) {
				fixed[i][j] = grid[i][j];
			} else {
				fixed[i][j] = 0;
			}
		}
	}
	vector<vector<int> > new_grid(m, vector<int>(n));
	for (long long s = 0; s < steps; s++) {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (fixed[i][j] >= 2) {
					new_grid[i][j] = fixed[i][j];
				}
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (fixed[i][j] >= 2) {
					continue;
				}
				int live_count = 0;
				for (int di = -1; di <= 1; di++) {
					for (int dj = -1; dj <= 1; dj++) {
						if (di == 0 && dj == 0) {
							continue;
						}
						int ni = i + di;
						int nj = j + dj;
						if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
							if (fixed[ni][nj] == 2) {
								live_count++;
							} else if (fixed[ni][nj] == 3) {
								live_count += 2;
							} else if (fixed[ni][nj] == 4) {
								live_count--;
							} else if (grid[ni][nj] == 1) {
								live_count += 1;
							}
						}
					}
				}
				if (grid[i][j] == 1) {
					if (live_count >= 2 && live_count <= 3) {
						new_grid[i][j] = 1;
					} else {
						new_grid[i][j] = 0;
					}
				} else {
					if (live_count == 3) {
						new_grid[i][j] = 1;
					} else {
						new_grid[i][j] = 0;
					}
				}
			}
		}
		grid.swap(new_grid);
	}
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			if (j > 0) {
				cout << " ";
			}
			cout << grid[i][j];
		}
		cout << endl;
	}
	return 0;
}