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
comments (?)
stdin 
Standard input is empty
stdout 
0
stderr 
Time elapsed: 0.009335 s.
https://ideone.com/fE31cJ
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!