Submission #1134742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134742		nai0610	Feast (NOI19_feast)	C++20	0 / 100	1095 ms	2740 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,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;
    int m=n;
    vector<int> a={-1};
    for (int i=1;i<=n;i++) {
    	int x;
    	cin >>x;
    	if (x) a.push_back(x);
    }
    n=a.size()-1;
    int i=1;
	set<pair<int,int>> s;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	while (i<=n) {
		int 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<=m;i++) res[i]=sum;
		for (int i=cnt-1;i>=1;i--) {
			while (cur>i) {
				while (1) {
					auto p=q.top();
					q.pop();
					it =s.lower_bound({p.second,-mod});
					if ((*it).first==p.second) break;
				}
				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);
					int nw=(*it).second+(*nex).second;
					cur +=(nw>0);
					if (nw>0) sum+=nw;
					s.erase(it);s.erase(nex);
					if (nw){
						s.insert({id,nw});
						q.push({abs(nw),id});
					}
				}
				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);
					int nw=(*it).second+(*pre).second;
					cur +=(nw>0);
					if (nw>0) sum+=nw;
					s.erase(it);s.erase(pre);
					if (nw){
						s.insert({id,nw});
						q.push({abs(nw),id});
					}
				}
				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);
					int nw=(*pre).second+(*it).second+(*nex).second;
					cur +=(nw>0);
					if (nw>0) sum+=nw;
					s.erase(pre);s.erase(it);s.erase(nex);
					if (nw){
						s.insert({id,nw});
						q.push({abs(nw),id});
					}
				}
			}
			res[i]=sum;
		}
		cout<<res[k]<<'\n';
	}
    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