Submission #1139916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139916		minhnguyent546	Feast (NOI19_feast)	C++20	100 / 100	140 ms	7556 KiB

feast

/**            
 * author      minhnguyent546
 * created_at  Sun, 2025-01-26 08:09:26
 * problem     https://oj.uz/problem/view/NOI19_feast
 **/           
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "cp/debug.h"
#else
#define debug(...)
#define cerr if (false) cerr
#endif

int n, k;
vector<int> arr;
vector<long long> pref;
void read() {
    cin >> n >> k;
    arr.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    pref.resize(n + 1);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + arr[i];
    }
}

long long sum(int l, int r) {
    assert(0 <= l && l <= r && r < n);
    return pref[r + 1] - pref[l];
}


const long long INF_LL = 0x3f3f3f3f3f3f3f3f;

namespace brute {
bool check() {
    return n <= 300;
}
void solve() {
    cerr << " *** [BRUTE] *** " << '\n';

    vector<long long> dp(n + 1, -INF_LL);
    vector<long long> ndp(n + 1);
    dp[0] = 0;
    for (int j = 0; j <= k; ++j) {
        for (int i = 1; i <= n; ++i) {
            ndp[i] = ndp[i - 1];
            if (j > 0) {
                for (int z = 0; z < i; ++z) {
                    ndp[i] = max(ndp[i], dp[z] + max(0LL, pref[i] - pref[z]));
                }
            }
        }
        dp.swap(ndp);
    }
    cout << dp[n] << '\n';

}
} // namespace brute

struct Line {
    int64_t a, b;
    const static int64_t INF_LL = 0x3f3f3f3f3f3f3f3f;
    Line(int64_t  _a = 0, int64_t _b = INF_LL): a(_a), b(_b) {}
    int64_t get(int64_t  x) {
        return (int64_t) a * x + b;
    }
    pair<int64_t, int64_t > intersect(const Line &other) {
        return {other.b - b, a - other.a};
    }
};

struct CHT {
    int sz;
    vector<Line> lines;
    CHT(): sz(0) {}
    bool can_remove_last(const Line &line) {
        auto [x1, y1] = lines[sz - 2].intersect(line);
        auto [x2, y2] = lines[sz - 1].intersect(line);
        return (__int128_t) x1 * y2 <= (__int128_t) x2 * y1;
    }
    void add_line(const Line &new_line) {   
        while (sz >= 2 && can_remove_last(new_line)) {
            lines.pop_back();
            --sz;
        }
        lines.emplace_back(new_line);
        ++sz;
    }
    long long get_min(long long x) {
        int low = 0, high = sz - 1;
        while (low < high) {
            int mid = low + (high - low + 1) / 2;
            if (lines[mid].get(x) > lines[mid + 1].get(x)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return lines[high].get(x);
    }
};

namespace sub7 {
bool check() {
    return true;
}
void solve() {
    cerr << " *** [SUB 7] *** " << '\n';
    long long low = -(long long) 1e18, high = 0;

    vector<long long> dp(n + 1);
    vector<int> min_seg(n + 1);

    auto gud = [&](long long lambda) -> bool {
        fill(dp.begin(), dp.end(), -INF_LL);
        dp[0] = 0;
        min_seg[0] = 0;

        long long max_f = dp[0] - pref[0];
        int max_f_min_seg = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            min_seg[i] = min_seg[i - 1];

            long long nval = max_f + pref[i] + lambda;
            if (nval > dp[i]) {
                dp[i] = nval;
                min_seg[i] = max_f_min_seg + 1;
            } else if (nval == dp[i]) {
                min_seg[i] = min(min_seg[i], max_f_min_seg + 1);
            }

            if (dp[i] - pref[i] > max_f) {
                max_f = dp[i] - pref[i];
                max_f_min_seg = min_seg[i];
            } else if (dp[i] - pref[i] == max_f) {
                max_f_min_seg = min(max_f_min_seg, min_seg[i]);
            }

        }
        return min_seg[n] <= k;
    };
    while (low < high) {
        long long mid = low + (high - low + 1) / 2;
        if (gud(mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    long long lambda = high;
    gud(lambda);
    long long ans = dp[n] - lambda * k;
    cout << ans << '\n';
}
} // namespace sub7


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    read();

    #ifdef LOCAL
        sub7::solve(); return 0;
        brute::solve(); return 0;
    #endif

    if (brute::check()) {
        brute::solve(); return 0;
    }

    if (sub7::check()) {
        sub7::solve(); return 0;
    }

    assert(false);
    
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29