Submission #1134726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134726		nai0610	Feast (NOI19_feast)	C++20	0 / 100	1095 ms	3648 KiB

feast

#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
// 
const int maxn =3e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,k,a[maxn];
ll res[maxn];
int main() {
    // freopen("../input.inp","r",stdin);
    // freopen("output.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >>n>>k;
    for (int i=1;i<=n;i++) cin >>a[i];
    int i=1;
	set<pair<int,ll>> s;
	priority_queue<pair<int,ll>,vector<pair<int,ll>>,greater<pair<int,ll>>> q;
	while (i<=n) {
		ll val=0;
		int j=i;
		while (j<=n&&a[i]*a[j]>=0) val+=a[j++];
		s.insert({i,val});
		i=j;
	}
	auto it=s.begin();
	while (!s.empty()&&(*it).second<0) s.erase(it),it=s.begin();
	if (!s.empty()){
		it =prev(s.end());
		while (!s.empty()&&(*it).second<0) s.erase(it),it=prev(s.end());
	}
	int cnt=s.size()/2+1;
	if (s.size()==0) {
		for (int i=1;i<=n;i++) res[i]=0;
		cout<<res[k];
	}
	else if (cnt==1) {
		for (int i=cnt;i<=n;i++) res[i]=(*s.begin()).second;
		cout<<res[k];
	}
	else {
		for (auto i=s.begin();i!=s.end();i++) q.push({abs((*i).second),(*i).first});
		int cur=cnt;
		int sum=0;
		for (auto i:s) {
			if (i.second>0) sum+=i.second;
		} 
		for (int i=cnt;i<=n;i++) res[i]=sum;
		for (int i=cnt-1;i>=1;i--) {
			it=s.begin();
			while (!s.empty()&&(*it).second<0) s.erase(it),it=s.begin();
			it =prev(s.end());
			while (!s.empty()&&(*it).second<0) s.erase(it),it=prev(s.end());
			while (cur>i) {
				auto p=q.top();
				q.pop();
				it =s.lower_bound({p.second,-inf});
				int id=(*it).first;
				if (it==s.begin()) {
					auto nex=next(it);
					cur-=((*it).second>=0)+((*nex).second>=0);
					sum-=((*it).second>=0?(*it).second:0)+
					   ((*nex).second>=0?(*nex).second:0);
					ll nw=(*it).second+(*nex).second;
					cur +=(nw>=0);
					if (nw>=0) sum+=nw;
					s.erase(it);s.erase(nex);
					s.insert({id,nw});
					q.push({abs((*it).second),(*it).first});
				}
				else if (it==prev(s.end())) {
					auto pre=prev(it);
					cur-=((*it).second>=0)+((*pre).second>=0);
					sum-=((*it).second>=0?(*it).second:0)+
					   ((*pre).second>=0?(*pre).second:0);
					ll nw=(*it).second+(*pre).second;
					cur +=(nw>=0);
					if (nw>=0) sum+=nw;
					s.erase(it);s.erase(pre);
					s.insert({id,nw});
					q.push({abs((*it).second),(*it).first});
				}
				else{
					auto pre=prev(it),nex=next(it);
					cur -= ((*pre).second>=0)+((*it).second>=0)+((*nex).second>=0);
					sum -= ((*pre).second>=0?(*pre).second:0)+
						   ((*it).second>=0?(*it).second:0)+
						   ((*nex).second>=0?(*nex).second:0);
					ll nw=(*pre).second+(*it).second+(*nex).second;
					cur +=(nw>=0);
					if (nw>=0) sum+=nw;
					s.erase(pre);s.erase(it);s.erase(nex);
					s.insert({id,nw});
					it=s.find({id,nw});
					q.push({abs((*it).second),(*it).first});
				}
			}
			res[i]=sum;
		}
		cout<<res[k];
	}
    return 0;
}

• 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