Submission #1296397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296397		chaitanyamehta	Feast (NOI19_feast)	C++20	0 / 100	65 ms	2764 KiB

feast

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

#define int long long
using i128 = __int128_t;

int n, k;
const int NEG_INF = LLONG_MIN / 4;
vector<int> a;

inline pair<int,int> better(const pair<int,int> &A, const pair<int,int> &B) {
    if (A.first != B.first) return (A.first > B.first) ? A : B;
    return (A.second >= B.second) ? A : B; // tie: prefer larger count
}

// Evaluate one lambda (penalty). Returns {best_adjusted_value, segments_used}
pair<int,int> eval_lambda(int lambda) {
    pair<int,int> dp0 = {0, 0};          // best up to i (maybe not ending at i)
    pair<int,int> dp1 = {NEG_INF, 0};    // best with a segment that ends exactly at i

    for (int i = 0; i < n; ++i) {
        pair<int,int> extend = { (dp1.first == NEG_INF ? NEG_INF : dp1.first + a[i]), dp1.second };
        pair<int,int> start  = { dp0.first + a[i] - lambda, dp0.second + 1 };
        dp1 = better(extend, start);
        dp0 = better(dp0, dp1);
    }
    return dp0;
}

int solve_lambda() {
    // Use safe, tight bounds derived from input to avoid overflow
    // sumAbs = sum |a[i]| <= n * 1e9 <= 3e14 (within 64-bit safely)
    long long sumAbs = 0;
    for (int i = 0; i < n; ++i) sumAbs += llabs(a[i]);
    int L = (int)(-sumAbs - 5);
    int R = (int)( sumAbs + 5);

    while (L < R) {
        int mid = L + ( (R - L + 1) >> 1 ); // upper-mid
        if (eval_lambda(mid).second >= k) L = mid;
        else R = mid - 1;
    }
    return L;
}

string toString128(i128 x) {
    if (x == 0) return "0";
    bool neg = x < 0;
    if (neg) x = -x;
    string s;
    while (x > 0) {
        int d = (int)(x % 10);
        s.push_back(char('0' + d));
        x /= 10;
    }
    if (neg) s.push_back('-');
    reverse(s.begin(), s.end());
    return s;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> k)) return 0;
    a.assign(n, 0);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // 1) find lambda boundary
    int bestLambda = solve_lambda();

    // 2) evaluate a few nearby lambdas to be robust against tie/boundary issues
    auto pL   = eval_lambda(bestLambda);
    auto pLm1 = eval_lambda(bestLambda - 1);
    // also check bestLambda+1 (optional, cheap)
    auto pLp1 = eval_lambda(bestLambda + 1);

    // 3) from each evaluation we can build a candidate answer for exactly K segments:
    // answer_candidate = adjusted_value + lambda * K
    // Note: adjusted_value = best( f(x) - lambda*x ) = f(c) - lambda*c  for the chosen c
    // And candidate = (f(c) - lambda*c) + lambda*K = f(c) + lambda*(K - c).
    // This is a valid candidate (possibly not the true maximum for exactly K), 
    // but checking neighbors covers boundary/tie cases.
    i128 cand1 = (i128)pL.first   + (i128)bestLambda * (i128)k;
    i128 cand2 = (i128)pLm1.first + (i128)(bestLambda - 1) * (i128)k;
    i128 cand3 = (i128)pLp1.first + (i128)(bestLambda + 1) * (i128)k;

    // 4) final answer is max among candidates and 0 (empty segments allowed)
    i128 ans128 = cand1;
    if (cand2 > ans128) ans128 = cand2;
    if (cand3 > ans128) ans128 = cand3;
    if (ans128 < 0) ans128 = 0;

    cout << toString128(ans128) << '\n';
    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