Submission #1147852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147852		alexbri	Feast (NOI19_feast)	C++20	100 / 100	288 ms	8652 KiB

feast

#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ld = long double;
#define rep(i, a, b) for (int i = a;  i < b; i++)
#define all(x) x.begin(), x.end()
#define pb(x) push_back(x)
#define sz(x) x.size()

pair<ll, int> f(vector<ll> &nums, ld x) {

    int n = nums.size();
    vector<ll> pf(n), dp(n);
    vi used(n);

    int best = 0;

    rep(i, 1, n) {
        pf[i] = pf[i - 1] + nums[i];
        dp[i] = pf[i] + dp[best] - pf[best] - x;
        used[i] = used[best] + 1;

        if (dp[i - 1] > dp[i]) {
            dp[i] = dp[i - 1];
            used[i] = used[i - 1];
        }

        if (dp[i] - pf[i] > dp[best] - pf[best])
            best = i;

    }

    best = 0;

    rep(i, 1, n)
        if (dp[i] > dp[best])
            best = i;
    
    return {dp[best], used[best]};
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll n, k; cin >> n >> k;
    vector<ll> nums(n + 1); 
    rep(i, 0, n) {
        ll x; cin >> x;
        nums[i + 1] = x;
    }

    ll l = 0, r = 1e13;     
    while (l <= r) {
        ll m = (l + r) / 2;
        ll sum, used; tie(sum, used) = f(nums, m);
        if (used <= k)
            r = m - 1;
        else
            l = m + 1;
    }
    
    cout << f(nums, l).first + l * ll(k) << "\n";
}

/*

    dp[l - 1] - pf[l - 1] - x

    Si voy a cerrar un subarreglo en r, me conviene que sea el que maximice el valor de 
    dp[l - 1] - pf[l - 1] - x

*/

• 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