Submission #533294

#	Time	Username	Problem	Language	Result	Execution time	Memory
533294		RyoPham	Feast (NOI19_feast)	C++14	45 / 100	1100 ms	30232 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];
set<pair<lli, int>> S;

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

int calc(lli lambda) {
    S.clear();
    S.insert(mp(0, 0));
    dp[0] = mp(0, 0);
    for(int i = 1; i <= n; ++i) {
        dp[i] = max(dp[i - 1], mp(S.rbegin()->fi + pref[i] - lambda, S.rbegin()->se + 1));
        dp[i] = max(dp[i], mp(dp[i - 1].fi - lambda, dp[i - 1].se + 1));
        S.insert(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: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29