fork download
  1. // Created by hoangvanthien
  2.  
  3. #include "bits/stdc++.h"
  4.  
  5. using namespace std;
  6.  
  7. #define FOR(i, x, y) for(int i = (x); i<=(y); ++i)
  8. #define REP(i, r) for(int i = 0; i < (r); ++i)
  9. #define DFOR(i, x, y) for(int i = (x); i>=(y); --i)
  10. #define db(x) cout << #x << " = " << x << endl;
  11. #define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it!=var.end(); ++it)
  12. #define forrit(it, var) for(__typeof(var.rbegin()) it = var.rbegin(); it!=var.rend(); ++it)
  13. #define pb push_back
  14. #define pf push_front
  15. #define mp make_pair
  16. #define F first
  17. #define S second
  18. #define II pair<int,int>
  19. #define LL long long
  20. #define lb lower_bound
  21. #define ub upper_bound
  22. #define LAST(x) (int)x.size()-1
  23. #define ld long double
  24. #define maximize(x, y) x=max(x,(y))
  25. #define minimize(x, y) x=min(x,(y))
  26.  
  27.  
  28. const int N = 502;
  29. const int oo = 1000000007;
  30. int n, money, R, d, e, q[6], Min[6], Max[6], ans, c[6], trace[N][6];
  31. II p[N][6];
  32.  
  33. void attemp(int x, int y) {
  34. if (x == R + 1) {
  35. maximize(ans, money);
  36. if (money == 12139) {
  37. FOR(i, 1, R) {
  38. FOR(j, 1, n) printf("%d ", trace[i][j]);
  39. puts("");
  40. }
  41. // exit(0);
  42. }
  43.  
  44. return;
  45. }
  46. if (y == n + 1) {
  47. FOR(i, 1, n)
  48. if (trace[x][i] > 0) money -= trace[x][i] * p[x][i].F, q[i] += trace[x][i];
  49. else money -= trace[x][i] * p[x][i].S, q[i] += trace[x][i];
  50. if (money < 0) {
  51. FOR(i, 1, n)
  52. if (trace[x][i] > 0) money += trace[x][i] * p[x][i].F, q[i] -= trace[x][i];
  53. else money += trace[x][i] * p[x][i].S, q[i] -= trace[x][i];
  54. return;
  55. }
  56. attemp(x + 1, 1);
  57. FOR(i, 1, n)
  58. if (trace[x][i] > 0) money += trace[x][i] * p[x][i].F, q[i] -= trace[x][i];
  59. else money += trace[x][i] * p[x][i].S, q[i] -= trace[x][i];
  60. return;
  61. }
  62. trace[x][y] = 0;
  63. if (Min[y] >= Max[y]) {
  64. attemp(x, y + 1);
  65. return;
  66. }
  67. if (Max[y] == p[x][y].S && q[y] != 0) {
  68. trace[x][y] = -q[y];
  69. attemp(x, y + 1);
  70. trace[x][y] = 0;
  71. }
  72.  
  73. if (Min[y] == p[x][y].F) {
  74. FOR(i, 0, c[y] - q[y]) {
  75. trace[x][y] = i;
  76. attemp(x, y + 1);
  77. trace[x][y] = 0;
  78. }
  79. return;
  80. }
  81. attemp(x, y + 1);
  82. // FOR(i, -q[y], c[y] - q[y]) {
  83. // trace[x][y] = i;
  84. // attemp(x, y + 1);
  85. // trace[x][y] = 0;
  86. // }
  87. }
  88.  
  89. int main() {
  90. #ifndef ONLINE_JUDGE
  91. freopen("input.inp", "r", stdin);
  92. // freopen("output.out", "w", stdout);
  93. #endif // ONLINE_JUDGE
  94. scanf("%d%d%d%d%d", &n, &money, &R, &d, &e);
  95. FOR(i, 1, n) scanf("%d", &c[i]);
  96. FOR(i, 1, n) Min[i] = oo, Max[i] = 0;
  97. FOR(i, 1, R) FOR(j, 1, n) {
  98. int x;
  99. scanf("%d", &x);
  100. p[i][j] = mp(x + d, x - e);
  101. minimize(Min[j], x + d);
  102. maximize(Max[j], x - e);
  103. }
  104. attemp(1, 1);
  105. printf("%d\n", ans);
  106.  
  107. cout << endl;
  108. cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  109. }
Success #stdin #stdout #stderr 0s 3504KB
stdin
Standard input is empty
stdout
0

stderr
Time elapsed: 0.009335 s.