Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2016
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <vector>
  2. #include <map>
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <ctime>
  7. #include <set>
  8. #include <functional>
  9. using namespace std;
  10.  
  11. int m, k;
  12.  
  13. map<pair<int, int>, pair<int, int>> was;
  14.  
  15.  
  16. pair<int, int> dfs(int n, int p) {
  17.     if (n <= 0) {
  18.         return {0, 0};
  19.     }
  20.     if (was.count({n, p}) != 0) {
  21.         return was[{n, p}];
  22.     }
  23.     pair<int, int> best = {-1, -1};
  24.     for (int i = 1; i <= k; ++i) {
  25.         auto cur = dfs(n - i, p ^ 1);
  26.         int add = i;
  27.         if (n - i < 0) {
  28.             add = m;
  29.         }
  30.         if (p == 1) {
  31.             if (cur.second + add > best.second) {
  32.                 best = cur;
  33.                 best.second += add;
  34.             } else if (cur.second + add == best.second && best.first > cur.first) {
  35.                 best = cur;
  36.             }
  37.         } else {
  38.             if (cur.first + add > best.first) {
  39.                 best = cur;
  40.                 best.first += add;
  41.             } else if (cur.first + add == best.first && best.second > cur.second) {
  42.                 best = cur;
  43.             }
  44.         }
  45.         if (n - i < 0) {
  46.             break;
  47.         }
  48.     }
  49.     was[{n, p}] = best;
  50.     return best;
  51. }
  52.  
  53.  
  54. int main() {
  55. #ifdef _DEBUG
  56.     freopen("input.txt", "r", stdin);
  57. #endif
  58.     int n;
  59.     scanf("%d %d %d", &n, &m, &k);
  60.     auto res = dfs(n, 0);
  61.     printf("%d %d", res.first, res.second);
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement