Submission #387415

#	Time	Username	Problem	Language	Result	Execution time	Memory
387415		saarang123	Feast (NOI19_feast)	C++17	100 / 100	320 ms	13108 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 3 * 100 * 1000 + 3;
int a[mxn], p[mxn], n, k;

array<int, 2> check(int m) {
	vector<int> dp(n + 1), cnt(n + 1);
	int besti = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1], cnt[i] = cnt[i - 1];
        if (dp[i] < dp[besti] + p[i] - p[besti] - m) {
            dp[i] = dp[besti] + p[i] - p[besti] - m;
            cnt[i] = cnt[besti] + 1;
        }
        if (dp[besti] - p[besti] < dp[i] - p[i]) besti = i;
    }
	return {dp[n], cnt[n]};
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    #ifdef saarang
    freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
    freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
    #endif
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
    	cin >> a[i];
    	p[i] = p[i - 1] + a[i];
    }
    int mn = 0, mx = 1e18;
    while(mn < mx) {
    	int mid = (mn + mx) >> 1;
    	if(check(mid)[1] > k)
    		mn = mid + 1;
    	else
    		mx = mid;
    }
    cout << check(mn)[0] + mn * k << '\n';
    return 0;
}

• 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