제출 #1296395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1296395		chaitanyamehta	Feast (NOI19_feast)	C++20	30 / 100	65 ms	2632 KiB

feast

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

#define int long long
int n, k;
const int NEG_INF = LLONG_MIN / 4; // very negative sentinel
vector<int> a;

// choose better by value; on tie prefer larger count
pair<int,int> better(const pair<int,int> &opt1, const pair<int,int> &opt2) {
    if (opt1.first != opt2.first) return (opt1.first > opt2.first) ? opt1 : opt2;
    return (opt1.second >= opt2.second) ? opt1 : opt2;
}

// evaluate lambda: returns {best_adjusted_value, segments_used}
pair<int,int> check(int lambda) {
    pair<int,int> dp1 = {NEG_INF, 0}; // best with a segment ending at i
    pair<int,int> dp0 = {0, 0};       // best up to i (not necessarily ending at i)

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

        dp1 = better(opt1, opt2);
        dp0 = better(dp0, dp1); // best up to i: either previous best or a segment ending at i
    }
    return dp0;
}

int solve() {
    // safe lambda bounds computed from input sums instead of LLONG extremes
    // sumAbs <= n * 1e9 <= 3e14 for constraints; we add some slack
    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 (safe)
        if (check(mid).second >= k) L = mid;
        else R = mid - 1;
    }
    return L;
}

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

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

    int bestLambda = solve();
    auto finalPr = check(bestLambda);

    // Recompose final answer: adjusted_value + lambda * K (use i128 to avoid overflow)
    __int128 res128 = (__int128)finalPr.first + (__int128)bestLambda * (__int128)k;
    long long result = (long long)res128;

    // Empty segments are allowed => answer >= 0
    result = max(0LL, result);
    cout << result << '\n';
    return 0;
}

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