Seletiva IOI 2016

somaint.cpp

// Ivan Carvalho
// Soma de Inteiros - Seletiva IOI - OBI 2016
// O(n*log(ai*N/K))
// Infelizmente esse problema apareceu previamente no Algorithmic Engagements
// Felizmente o link para submeter existe : https://tinyurl.com/somaint2016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN = 1e6 + 10;
ll soma[MAXN],N,K;
vector<ll> entrada;
ii dp[MAXN];
ii checa(ll W){
	ii best = ii(0,0);
	for(ll i = 1;i<=N;i++){
		dp[i] = dp[i-1];
		dp[i] = max(dp[i], ii(soma[i] + best.first - W, best.second + 1 ) );
		best = max(best, ii(dp[i].first - soma[i],dp[i].second)  );
	}
	return dp[N];
}
int main(){
	cin.tie(0);ios_base::sync_with_stdio(0);
	cin >> N >> K;
	ll positivo = 0;
	for(ll i = 1;i<=N;i++){
		ll x;
		cin >> x;
		if(x > 0) positivo++;
		if(entrada.empty()) entrada.push_back(x);
		else if(x >0 && entrada.back() >= 0) entrada.back() += x;
		else if(x < 0 && entrada.back() <= 0) entrada.back() += x;
		else entrada.push_back(x);
	}
	if(positivo == 0){
		cout << 0 << endl;
		return 0;
	}
	N = entrada.size();
	for(ll i = 1;i<=N;i++) soma[i] = soma[i-1] + entrada[i-1];
	ll ini = 0, fim = (ll)1e15,resp = 0,meio;
	while(ini <= fim){
		meio = (ini+fim)/2;
		if(checa(meio).second >= K){
			resp = meio;
			ini = meio + 1;
		}
		else{
			fim = meio - 1;
		}
	}
	printf("%lld\n",checa(resp).first + resp*K);
	return 0;
}