Submission #1057617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057617		ghostlywalrus	Feast (NOI19_feast)	C++17	100 / 100	155 ms	10404 KiB

feast

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define int long long
#define PI pair<int,int>
#define f first
#define s second
#define pb push_back
#define szo(x) ((int)x.size())

const int INF = 1e18;
const int maxn = 3e5+10;

int n, k;
int nums[maxn];
int dp[maxn];
int cnt[maxn];

PI solve(int m){
	 for (int i = 0; i <= n; ++i) dp[i] = 0, cnt[i] = 0;
	 int best = 0;
	 int idbest = 0;
		
	 for (int i = 1; i <= n; ++i){
	 	dp[i] = dp[i-1];
		cnt[i] = cnt[i-1];
		best += nums[i];

		if (best-m > dp[i]){
	 		dp[i] = best-m;
			cnt[i] = cnt[idbest] + 1; 
		}

		if ((dp[i] > best) || ((dp[i] == best) && cnt[i] <= cnt[idbest])){
	 		best = dp[i];
			idbest = i;
		}
	 }

	 return {dp[n], cnt[n]}; 
}


int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;

	for (int i = 1; i <= n; ++i) cin >> nums[i];

	int x = 1e18;
	for (int b = 1e18; b >= 1; b >>= 1){
	 	while (x-b >= 0 && solve(x-b).s <= k) x -= b;
	}

	cout << solve(x).f + k * x << '\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