Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.74 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define F first
  5. #define S second
  6. #define IDB if (debug)
  7.  
  8. typedef long long ll;
  9. typedef double ld;
  10. typedef pair <int, int> pii;
  11. const int SZ = 3e5 + 4;
  12. const int oo = 1e9 + 4;
  13. const int mod = 1e9 + 7;
  14. const bool debug = 0;
  15.  
  16. string s;
  17. ll n, x, t, pr, sum, mn, mx, ok, ans, ind1;
  18. ll a[SZ], p[SZ], l[SZ];
  19. ll indmn, indmn2;
  20.  
  21. void read() {
  22. cin >> n >> x;
  23. for (int i = 1; i <= n; i++) {
  24. cin >> a[i];
  25. }
  26. }
  27.  
  28. void solve() {
  29. if (x >= 0) {
  30. for (int i = 1; i <= n; i++) {
  31. sum += a[i];
  32. if (sum < pr) pr = sum;
  33. ok = max(ok, sum - pr);
  34. }
  35. cout << max(ok, ok * x);
  36. return;
  37. }
  38.  
  39. for (int i = 1; i <= n; i++)
  40. p[i] = p[i - 1] + a[i];
  41.  
  42. for (int i = n; i > 0; i--)
  43. l[i] = l[i + 1] + a[i];
  44.  
  45. pr = 0;
  46. for (int i = 1; i <= n; i++) {
  47. pr = min(pr, p[i]);
  48. p[i] = p[i] - pr;
  49.  
  50. // cout << p[i] << ' ';
  51. }
  52. //cout << endl;
  53.  
  54. pr = 0;
  55. for (int i = n; i > 0; i--) {
  56. pr = min(pr, l[i]);
  57. l[i] = l[i] - pr;
  58. // cout << l[i] << ' ';
  59.  
  60. }
  61. //cout << endl;
  62.  
  63. pr = 0;
  64. ans = 0;
  65. sum = 0;
  66. for (int i = 1; i <= n; i++) {
  67. sum += a[i];
  68.  
  69. if (sum > pr) {
  70. pr = sum;
  71. ind1 = i;
  72. }
  73.  
  74. ll ns = (sum - pr) * x + l[i + 1] + p[ind1];
  75. if (ind1 == i) ns = l[i + 1] + p[ind1];
  76. // cout << ns << ' ' << sum << ' ' << pr << ' ' << ind1 << ' ' << i <<' ' << p[ind1] << ' ' << l[i + 1] << endl;
  77. ans = max(ans, ns);
  78. }
  79.  
  80. cout << max(ans, p[n]);
  81. }
  82.  
  83. signed main(){
  84. ios::sync_with_stdio(0);
  85. cin.tie(NULL);
  86.  
  87. read();
  88. solve();
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement