Submission #1157051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157051		shn	Feast (NOI19_feast)	C++20	45 / 100	1096 ms	37924 KiB

feast

/*
	Dimash ne katai!!!
	shnurok krash))
	Serikbay777 tozhe krash))
*/
#include <bits/stdc++.h>
#define pll pair < long long , long long >
#define len(s) (long long)(s.size())
#define all(x) x.begin() , x.end()
#define pii pair < int , int >
#define pofik continue
#define int long long
#define pb push_back
#define ins insert
#define F first
#define S second
const long long N = 3e5 + 77 , inf = 1e18 + 77 , MOD = 1e9 + 7;
const long double eps = 1e-9;
using namespace std;
int T = 1;
int binpow(int a , int b){
	if(!b) return 1;
	int val = binpow(a , b / 2);
	if(b % 2 == 0) return val * val % MOD;
	else return val * val % MOD * a % MOD;
}

int n , k;
int a[N], pref[N];

pll check(long double lmd){
	pair < long double , int > dp[n + 5];
	for(int i = 1; i <= n; i++) dp[i] = {-inf , 0};
	dp[0] = {0 , 0};
	set < pair <long double , int > > st;
	st.ins({0 , 0});
	for(int i = 1; i <= n; i++){
		dp[i] = dp[i - 1];
		if(dp[i].F == (st.rbegin() -> first) + pref[i] - lmd) dp[i].S = min(dp[i].S , (st.rbegin() -> second) + 1);
		else dp[i] = max(dp[i] , {(st.rbegin() -> first) + pref[i] - lmd , (st.rbegin() -> second) + 1});
		st.ins({dp[i].F - pref[i] , dp[i].S});
	}
	return dp[n];
}

void solve(){
	cin >> n >> k;
	for(int i = 1 ; i <= n; i++){
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	int l = 0 , r = 1e14 , res = 0;
	while(l <= r){
		long double mid = (l + r) / 2;
		if(check(mid).S >= k){
			l = mid + 1;
			res = mid;
		}
		else{
			r = mid - 1;
		}
	}
	cout << check(res).F + k * res;
}

signed main(){
	// cin >> T;
    for(int cas = 1; cas <= T; cas++){
    	// cout << "Case " << cas << ":\n";
    	solve();
    }
}
/*
	 ___      __                      _
	|   \    | |          _____      | |  _
	| |\ \   | |  __  __ |  __ \     | | (_)
	| | \ \  | | | |  | || |  \_\__ _| |  _
	| |  \ \ | | | |  | || |    / _` | | | |
	| |   \ \| | | |__| || |   / (_| | | | |
	|_|    \___| |______||_|    \_,__|_| |_|
	
	Created by: Moldiyar Abay
 	
*/

• 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