Submission #987514

#	Time	Username	Problem	Language	Result	Execution time	Memory
987514		tfgs	Feast (NOI19_feast)	C++17	0 / 100	1057 ms	27060 KiB

feast

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

#ifdef LOCAL
#include "algo/debug.h"
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }

int n, k;
vi a;
// returns {score, number of segments} with penalty lmb for making a new subarray
array<int, 2> calc(int lmb) {
    V<V<array<int, 2>>> dp(n+1, V<array<int, 2>>(2));
    for (int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        dp[i][1] = max(array<int, 2>{dp[i-1][0][0]+a[i-1]-lmb, dp[i-1][0][1]+1},
                       array<int, 2>{dp[i-1][1][0]+a[i-1], dp[i-1][1][1]});
    }
    return max(dp[n][0], dp[n][1]);
}

void solve() {
    cin >> n >> k;
    a.resize(n); for (int i = 0; i < n; i++) cin >> a[i];
    int lo = -1, hi = 1e18;
    while (hi-lo > 1) {
        int m = (lo+hi)/2;
        auto res = calc(m);
        res[1] >= k ? lo = m : hi = m;
    }
    auto ans = calc(lo);
    cout << ans[0]+ans[1]*k << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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