Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #include <algorithm>
- #include <iomanip>
- #include <vector>
- #include <set>
- #include <map>
- #include <queue>
- #include <string>
- #include <initializer_list>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- int const INF = 1e9;
- int const mod = 1e9 + 7;
- ll const INF_LL = 1e18;
- ld const eps = 1e-8;
- ld const PI = acos(-1);
- struct ls {
- long long sum;
- long long ans;
- long long pref;
- long long suff;
- ls() {};
- ls(long long const& s, long long const& a, long long const& tof, long long const& froml) {
- sum = s;
- ans = a;
- pref = tof;
- suff = froml;
- }
- };
- ls tree[4000008];
- ls a[1000002];
- long long o = 1;
- void update(ls & id, ls v, ls w) {
- id.sum = v.sum + w.sum;
- id.pref = (long long)max(v.pref, v.sum + w.pref);
- id.suff = (long long)max(w.suff, w.sum + v.suff);
- id.ans = (long long)max(v.ans, w.ans);
- id.ans = (long long)max(id.ans, id.pref);
- id.ans = (long long)max(id.ans, id.suff);
- id.ans = (long long)max(id.ans, v.suff + w.pref);
- return;
- }
- void build(int const& n) {
- while (o < n) o *= 2;
- for (int i = o; i < o + n; i++) tree[i] = a[i - o];
- for (int i = o - 1; i >= 1; i--) update(tree[i], tree[2 * i], tree[2 * i + 1]);
- return;
- }
- ls getans(int v, int lv, int rv, int l, int r) {
- if (rv <= l || r <= lv) return ls(0, -INF_LL, -INF_LL, -INF_LL);
- if (l <= lv && rv <= r) return tree[v];
- int mv = (lv + rv) / 2;
- ls temp;
- update(temp, getans(2 * v, lv, mv, l, r), getans(2 * v + 1, mv, rv, l, r));
- return temp;
- }
- int main() {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- freopen("eaze_zadacha_ot_glebosa.in", "r", stdin);
- freopen("eaze_zadacha_ot_glebosa.out", "w", stdout);
- ll n, k, res;
- cin >> n >> k >> res;
- ll sum = 0;
- bool wasbelow = false;
- for (int i = 0; i < n; i++) {
- ll q;
- cin >> q;
- sum += q;
- if (q < 0) wasbelow = true;
- a[i] = ls(q, q, q, q);
- }
- ll ans;
- if (!wasbelow) {
- ans = sum * (k + 1);
- } else {
- sum = 0;
- ll left = -INF_LL;
- for (int i = 0; i < n; i++) {
- sum += a[i].sum;
- left = max(left, sum);
- }
- sum = 0;
- ll right = -INF_LL;
- for (int i = n; i >= 0; i--) {
- sum += a[i].sum;
- right = max(right, sum);
- }
- build(n);
- ls f = getans(1, 1, o + 1, 1, n + 1);
- if (f.ans == sum) ans = f.ans * (k + 1); else ans = left + f.ans * (k - 1) + right;
- }
- if (!k) ans = sum;
- (ans > res) ? cout << "AGRONOM)\n" << ans : cout << "KAK TAK TO(";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement