Submission #1131026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131026		dibamboo	Feast (NOI19_feast)	C++20	100 / 100	121 ms	9844 KiB

feast

/* author : Dinmukhammed ^_^ */

#include <map>
#include <set>
#include <unordered_set>
#include <list>
#include <cmath>
#include <ctime>                         																											
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
#include <complex>

using namespace std;

#define F first
#define S second
#define sz size()
#define ll long long
#define ld long double


const int N = 4e5+3;
const ll inf = 1e18;

ll a[N] , p[N];
pair <ll , int> dp[N];
int n;

pair <ll , int> get(ll lam){
	dp[0] = {0ll , (int)0};
	set <pair <ll , int>> st;
	pair <ll , int> mx = dp[0];
	for(int i = 1; i <= n; i++){
		mx = max({dp[i - 1].F - p[i] , dp[i - 1].S} , mx);
		dp[i] = mx;
		dp[i].F += lam + p[i];
		dp[i].S--;
		dp[i] = max(dp[i - 1] , dp[i]);
		mx = max({dp[i].F - p[i] , dp[i].S} , mx);
	}
	dp[n].S = -dp[n].S;
	return dp[n];
}

void Main(){
	ll k; cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
	}
	ll l = -(ll)1e18 , r = 0 , res = -(ll)1e18;
	while(r >= l){
		ll md = (r + l) / 2;
		if(get(md).S <= k){
			res = md;
			l = md + 1;
		}
		else r = md - 1;
	}
	cout << get(res).F - res * k;
}


signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tt = 1;
	// cin >> tt;
	while(tt--) Main();
}

• 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