# Cod sursa(job #2355468)

Utilizator Data 26 februarie 2019 09:14:27 Ferma 20 cpp-64 done Arhiva de probleme 3.08 kb
``````#include<bits/stdc++.h>
using namespace std;
ifstream f("ferma.in");
ofstream g("ferma.out");
int n, k;
int ans = 0, s;
int v[10002], ord[10002], sum[10002];
int tt[10002];
int rg[10002];
bool was[10002];
bool cmp(int a, int b)
{
return v[a] > v[b];
}
int Find(int a)
{
if(tt[a] == a)
return a;
return tt[a] = Find(tt[a]);
}
void Union(int a, int b)
{
if(Find(a) == Find(b))
return;
a = Find(a), b = Find(b);
multiset<int> ::iterator it;
it = sume.lower_bound(sum[Find(a)]);
if(*it == sum[Find(a)])
sume.erase(it), s -= *it;
else
{
}
it = sume.lower_bound(sum[Find(b)]);
if(*it == sum[Find(b)])
sume.erase(it), s -= *it;
else
{
}
sume.insert(sum[Find(a)] + sum[Find(b)]);
s += sum[Find(a)] + sum[Find(b)];
if(rg[a] > rg[b])
{
tt[b] = a;
rg[a] += rg[b];
sum[a] += sum[b];
}
else
{
tt[a] = b;
rg[b] += rg[a];
sum[b] += sum[a];
}
}
int main()
{
f >> n >> k;
for(int i = 1; i <= n; ++i)
f >> v[i], ord[i] = i, tt[i] = i, rg[i] = 1, sum[i] = v[i];
sort(ord+1, ord+n+1, cmp);
for(int i = 1; i <= n; ++i)
{
int val = ord[i];
was[val] = 1;
sume.insert(v[val]);
s += v[val];
{
sume.insert(*it);
s += *it;
}
while(sume.size() > k)
{
multiset<int> ::iterator it = sume.begin();
s -= *it;
sume.erase(it);
}
ans = max(ans, s);
if(val > 1 && was[val - 1])
Union(Find(val - 1), Find(val));
else
if(val == 1 && was[n])
Union(Find(n), Find(val));
{
sume.insert(*it);
s += *it;
}
while(sume.size() > k)
{
multiset<int> ::iterator it = sume.begin();
s -= *it;
sume.erase(it);
}
ans = max(ans, s);
if(val < n && was[val + 1])
Union(Find(val), Find(val + 1));
else
if(val == n && was[1])
Union(Find(val), Find(1));
{
sume.insert(*it);
s += *it;
}
while(sume.size() > k)
{
multiset<int> ::iterator it = sume.begin();
s -= *it;