Submission #533297

#	Time	Username	Problem	Language	Result	Execution time	Memory
533297		RyoPham	Feast (NOI19_feast)	C++14	100 / 100	155 ms	11588 KiB

feast

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second
#define mp make_pair

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 3e5 + 5;
const int lim = 1e9 + 9;

int n, k;
int a[maxn];

lli pref[maxn];

lli sum = 0;

pair<lli, int> dp[maxn];

void read_input() {
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
}

int calc(lli lambda) {
    pair<lli, int> best = mp(0, 0);
    dp[0] = mp(0, 0);
    for(int i = 1; i <= n; ++i) {
        dp[i] = max(dp[i - 1], mp(best.fi + pref[i] - lambda, best.se + 1));
        dp[i] = max(dp[i], mp(dp[i - 1].fi - lambda, dp[i - 1].se + 1));
        best = max(best, mp(dp[i].fi - pref[i], dp[i].se));
    }
    return dp[n].se;
}

void solve() {
    pref[0] = 0;
    for(int i = 1; i <= n; ++i) {
        pref[i] = pref[i - 1] + a[i];
    }

    lli low = -maxn * 1LL * lim, high = maxn * 1LL * lim;
    while(low <= high) {
        lli mid = (low + high) / 2;
        if(calc(mid) >= k) low = mid + 1;
        else high = mid - 1;
    }

    calc(high);

    cout << dp[n].fi + high * dp[n].se << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
  
    read_input();
    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