Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <map>
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <ctime>
- #include <set>
- #include <functional>
- using namespace std;
- int m, k;
- map<pair<int, int>, pair<int, int>> was;
- pair<int, int> dfs(int n, int p) {
- if (n <= 0) {
- return {0, 0};
- }
- if (was.count({n, p}) != 0) {
- return was[{n, p}];
- }
- pair<int, int> best = {-1, -1};
- for (int i = 1; i <= k; ++i) {
- auto cur = dfs(n - i, p ^ 1);
- int add = i;
- if (n - i < 0) {
- add = m;
- }
- if (p == 1) {
- if (cur.second + add > best.second) {
- best = cur;
- best.second += add;
- } else if (cur.second + add == best.second && best.first > cur.first) {
- best = cur;
- }
- } else {
- if (cur.first + add > best.first) {
- best = cur;
- best.first += add;
- } else if (cur.first + add == best.first && best.second > cur.second) {
- best = cur;
- }
- }
- if (n - i < 0) {
- break;
- }
- }
- was[{n, p}] = best;
- return best;
- }
- int main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #endif
- int n;
- scanf("%d %d %d", &n, &m, &k);
- auto res = dfs(n, 0);
- printf("%d %d", res.first, res.second);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement