Submission #389978

#	Time	Username	Problem	Language	Result	Execution time	Memory
389978		smax	Feast (NOI19_feast)	C++17	100 / 100	351 ms	12744 KiB

feast

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define DEBUG(...) 6
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template <typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << s.substr(0, i) << " = " << x << " | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i=0; i<n; i++)
        cin >> a[i];

    auto solve = [&] (long long c) -> pair<bool, long long> {
        vector<long long> pref(n + 1);
        for (int i=0; i<n; i++)
            pref[i+1] = a[i] + pref[i];
        vector<__int128_t> dp(n + 1);
        vector<int> cnt(n + 1);
        dp[0] = 0;
        int mx = 0;
        for (int i=0; i<n; i++) {
            dp[i+1] = dp[i];
            cnt[i+1] = cnt[i];
            if (dp[mx] + pref[i+1] - pref[mx] - c > dp[i]) {
                dp[i+1] = dp[mx] + pref[i+1] - pref[mx] - c;
                cnt[i+1] = cnt[mx] + 1;
            }
            if (dp[i+1] - pref[i+1] > dp[mx] - pref[mx])
                mx = i + 1;
        }
        return {cnt[n] <= k, dp[n] + c * cnt[n]};
    };

    long long l = 0, r = 1e18;
    while (l < r) {
        long long m = (l + r) / 2;
        if (solve(m).first)
            r = m;
        else
            l = m + 1;
    }
    cout << solve(l).second << "\n";

    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