Submission #1072170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072170		NeroZein	Tricks of the Trade (CEOI23_trade)	C++17	25 / 100	3243 ms	2097152 KiB

trade

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

const long long INF = 1e15 + 15;

void maximize(long long& x, long long y) {
	x = max(x, y); 
}

inline void dfs(int i, int st, int ck, vector<bool>& used, vector<vector<vector<bool>>>& vis, vector<vector<vector<vector<array<int, 3>>>>>& path) {
	if (vis[i][st][ck] == true) {
		return;
	}
	vis[i][st][ck] = true;
	if (i == 0 && ck == 1) {
		used[0] = true; 
	}
	for (auto [pi, pst, pk] : path[i][st][ck]) {
		if (pk == ck - 1) {
			used[i] = true; 
		}
		dfs(pi, pst, pk, used, vis, path); 
	}
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> c(n), s(n);
	for (int i = 0; i < n; ++i) {
	  cin >> c[i];
	}
	for (int i = 0; i < n; ++i) {
	  cin >> s[i];
	}
	vector<vector<vector<bool>>> vis(n, vector<vector<bool>> (3, vector<bool> (k + 1)));
	vector<vector<vector<long long>>> dp(n, vector<vector<long long>> (3, vector<long long> (k + 1)));
	function<long long(int, int, int)> bt = [&](int i, int st, int ck) {
		if (ck > k) {
			return -INF;
		}
		if (i == n) {
			return (st == 2 && ck == k ? 0 : -INF);
		}
		long long& ret = dp[i][st][ck];
		if (vis[i][st][ck]) {
			return ret;
		}
		vis[i][st][ck] = true; 
		ret = -INF;
		if (st == 0) {
			ret = bt(i + 1, 0, 0);
			ret = max(ret, bt(i + 1, 1, 1) + s[i] - c[i]);
		} else if (st == 1) {
			ret = bt(i + 1, 1, ck) - c[i];
			if (ck + 1 < k) {
				ret = max(ret, bt(i + 1, 1, ck + 1) + s[i] - c[i]);				
			} else {
				ret = max(ret, bt(i + 1, 2, ck + 1) + s[i] - c[i]); 
			}
		} else {
			ret = bt(i + 1, 2, ck); 
		}
		return ret; 
	};
	vector<int> used(n); 
	function<void(int, int, int)> path = [&](int i, int st, int ck) {
		if (i == n) {
			return;
		}
		if (vis[i][st][ck] == true) {
			return;
		}
		vis[i][st][ck] = true;
		long long ret = dp[i][st][ck];
		if (st == 0) {
			if (ret == bt(i + 1, 0, 0)) {
				path(i + 1, 0, 0);
			}
			if (ret == bt(i + 1, 1, 1) + s[i] - c[i]) {
				used[i] = 1; 
				path(i + 1, 1, 1);
			}
		} else if (st == 1) {
			if (ret == bt(i + 1, 1, ck) - c[i]) {
				path(i + 1, 1, ck);
			}
			if (ck + 1 < k && ret == bt(i + 1, 1, ck + 1) + s[i] - c[i]) {
				used[i] = 1; 
				path(i + 1, 1, ck + 1);
			} 
			if (ck + 1 == k && ret == bt(i + 1, 2, ck + 1) + s[i] - c[i]) {
				used[i] = 1;
				path(i + 1, 2, ck + 1);
			}
		} else {
			path(i + 1, 2, ck); 
		}
	};
	cout << bt(0, 0, 0) << '\n';
	for (int i = 0; i < n; ++i) {
	  for (int j = 0; j < 3; ++j) {
		  for (int l = 0; l <= k; ++l) {
			  vis[i][j][l] = false; 
		  }
	  }
	}
	path(0, 0, 0);
	for (int i = 0; i < n; ++i) {
		cout << used[i];
	}
	return 0; 
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 10
• Subtask 2: 5 / 10
• Subtask 3: 5 / 10
• Subtask 4: 10 / 25
• Subtask 5: 0 / 45