Submission #1319490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319490		jxu	Feast (NOI19_feast)	C++20	100 / 100	194 ms	6208 KiB

feast

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tuple<int, int, int> ti;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#define debugArr(...)
#endif

const int MOD = 1000000007;
const char nl = '\n';

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

void solve() {
    int n, k; cin >> n >> k;
    vi A(n);
    rep(i, 0, n) cin >> A[i];

    typedef pair<ll, ll> en;
    const ll inf = 1e18;
    auto calc = [&] (ll m) {
        // dp[i]: max value from i..n given most recent starts at i
        // I am maxing, so I want to min intervals
        vector<en> dp(n + 1);
        en mx = {0, 0};
        for (int i = n - 1; i >= 0; i--) {
            // start new interval
            en cand = mx;
            cand.first += max(A[i] - m, -m);
            cand.second++;
            dp[i] = cand;


            // extends interval
            cand = dp[i + 1];
            if (cand.second != 0) {
                cand.first += A[i];
                dp[i] = max(dp[i], cand);
            }
            mx = max(dp[i], mx);
        }

        return mx;
    };

    // low: use all ops, high: use no ops
    ll low = -1;
    ll high = 1e15;
    while(low + 1 < high) {
        ll mid = low + (high - low)/2;
        en res = calc(mid);
        ll ops = res.second;
        if (ops >= k) {
            low = mid;
        } else {
            high = mid;
        }
    }
    en res = calc(low);
    cout << res.first + (ll)k * low << nl;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

• 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