Submission #1131006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131006		dibamboo	Feast (NOI19_feast)	C++20	0 / 100	1097 ms	28216 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
#define int ll


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;
	st.insert(dp[0]);
	for(int i = 1; i <= n; i++){
		dp[i] = *(--st.end());
		dp[i].F += lam + p[i];
		dp[i].S++;
		dp[i] = max(dp[i - 1] , dp[i]);
		st.insert({dp[i].F - p[i] , dp[i].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)1e14 , r = (ll)1e14 , res = -(ll)1e14;
	while(r >= l){
		ll md = (r + l) / 2;
		if(get(md).S <= k){
			res = md;
			l = md + 1;
		}
		else r = md - 1;
	}
	cout << max(get(res).F - res * k , 0ll);
}


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

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29