Advertisement
Guest User

Untitled

a guest
Sep 29th, 2016
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.51 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iomanip>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <queue>
  10. #include <string>
  11. #include <initializer_list>
  12. #include <cassert>
  13.  
  14. using namespace std;
  15.  
  16. typedef long long ll;
  17. typedef long double ld;
  18. int const INF = 1e9;
  19. int const mod = 1e9 + 7;
  20. ll const INF_LL = 1e18;
  21. ld const eps = 1e-8;
  22. ld const PI = acos(-1);
  23.  
  24.  
  25. struct ls {
  26. long long sum;
  27. long long ans;
  28. long long pref;
  29. long long suff;
  30. ls() {};
  31. ls(long long const& s, long long const& a, long long const& tof, long long const& froml) {
  32. sum = s;
  33. ans = a;
  34. pref = tof;
  35. suff = froml;
  36. }
  37. };
  38.  
  39. ls tree[4000008];
  40. ls a[1000002];
  41. long long o = 1;
  42.  
  43. void update(ls & id, ls v, ls w) {
  44. id.sum = v.sum + w.sum;
  45. id.pref = (long long)max(v.pref, v.sum + w.pref);
  46. id.suff = (long long)max(w.suff, w.sum + v.suff);
  47. id.ans = (long long)max(v.ans, w.ans);
  48. id.ans = (long long)max(id.ans, id.pref);
  49. id.ans = (long long)max(id.ans, id.suff);
  50. id.ans = (long long)max(id.ans, v.suff + w.pref);
  51. return;
  52. }
  53.  
  54. void build(int const& n) {
  55. while (o < n) o *= 2;
  56. for (int i = o; i < o + n; i++) tree[i] = a[i - o];
  57. for (int i = o - 1; i >= 1; i--) update(tree[i], tree[2 * i], tree[2 * i + 1]);
  58. return;
  59. }
  60.  
  61. ls getans(int v, int lv, int rv, int l, int r) {
  62. if (rv <= l || r <= lv) return ls(0, -INF_LL, -INF_LL, -INF_LL);
  63. if (l <= lv && rv <= r) return tree[v];
  64. int mv = (lv + rv) / 2;
  65. ls temp;
  66. update(temp, getans(2 * v, lv, mv, l, r), getans(2 * v + 1, mv, rv, l, r));
  67. return temp;
  68. }
  69.  
  70. int main() {
  71. //freopen("input.txt", "r", stdin);
  72. //freopen("output.txt", "w", stdout);
  73. freopen("eaze_zadacha_ot_glebosa.in", "r", stdin);
  74. freopen("eaze_zadacha_ot_glebosa.out", "w", stdout);
  75. ll n, k, res;
  76. cin >> n >> k >> res;
  77. ll sum = 0;
  78. bool wasbelow = false;
  79. for (int i = 0; i < n; i++) {
  80. ll q;
  81. cin >> q;
  82. sum += q;
  83. if (q < 0) wasbelow = true;
  84. a[i] = ls(q, q, q, q);
  85. }
  86. ll ans;
  87. if (!wasbelow) {
  88. ans = sum * (k + 1);
  89. } else {
  90. sum = 0;
  91. ll left = -INF_LL;
  92. for (int i = 0; i < n; i++) {
  93. sum += a[i].sum;
  94. left = max(left, sum);
  95. }
  96. sum = 0;
  97. ll right = -INF_LL;
  98. for (int i = n; i >= 0; i--) {
  99. sum += a[i].sum;
  100. right = max(right, sum);
  101. }
  102. build(n);
  103. ls f = getans(1, 1, o + 1, 1, n + 1);
  104. if (f.ans == sum) ans = f.ans * (k + 1); else ans = left + f.ans * (k - 1) + right;
  105. }
  106. if (!k) ans = sum;
  107. (ans > res) ? cout << "AGRONOM)\n" << ans : cout << "KAK TAK TO(";
  108. return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement