Submission #1170837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170837		mr_az	Feast (NOI19_feast)	C++20	100 / 100	626 ms	22488 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_JUDGE
	#include<local_debug>
#else
	#define debug(...) 1
#endif
#define ls (p<<1)
#define rs (p<<1|1)
#define pb push_back
#define int long long
#define eb emplace_back
#define lowbit(x) (x&-x)
#define rint register int
#define alls(a) a.begin(),a.end()
#define mem(a,b) memset(a,b,sizeof a)
typedef long long ll;
typedef __int128 i128;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
bool ST;
const int inf=0x3f3f3f3f;
const ll INF=1e18;
template<typename T>
void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    x*=f;
}
template<typename T,typename ... Args>
void read(T &x, Args &... y){read(x);read(y...);}
namespace Mr_Az{
	const int N=3e5+8;
	int T=1;
	int n,k,m,ans,cnt;
	bool f=0;
	int a[N],b[N];
	bool vis[N];
	set<int> s;
	set<pii> q;
	inline int abs(int x){return x<0?-x:x;}
	inline void solve(){
		read(n,k);
		for(rint i=1;i<=n;i++) read(a[i]);a[0]=-1;
		for(rint i=1;i<=n;i++){	
			f|=(a[i]>=0);
			if(f){
				m+=!((a[i-1]<0&&a[i]<0)||(a[i-1]>=0&&a[i]>=0));
				b[m]+=a[i];
			}
		}
		if(a[n]<0) m--;
		b[0]=b[m+1]=0;
		for(rint i=1;i<=m;i++){
			cerr<<b[i]<<" ";
			if(b[i]>=0) cnt++;
			q.insert({abs(b[i]),i});
			s.insert(i);
		}cerr<<endl;
		while(cnt>k){
			cerr<<cnt<<" "<<k<<endl;
			auto [x,i]=*q.begin();
			auto it=s.lower_bound(i),pre=it,nxt=it;
			pre--;nxt++;
			if(b[i]<0&&(it==s.begin()||nxt==s.end())){
				s.erase(it);
				q.erase(q.begin());
				continue;
			}
			vector<int> t;t.clear();
			if(b[i]>=0) cnt--;
			if(it!=s.begin()){
				b[i]+=b[*pre];
				t.pb(*pre);
			}
			if(nxt!=s.end()){
				b[i]+=b[*nxt];
				t.pb(*nxt);
			}
			q.erase(q.begin());
			for(auto xx:t){
				if(b[xx]>=0) cnt--;
				s.erase(s.find(xx));
				auto it1=q.find({abs(b[xx]),xx});
				if(it1!=q.end()) q.erase(it1);
			}
			q.insert({abs(b[i]),i});
			if(b[i]>=0) cnt++;
		}
		while(q.size()){
			auto [x,i]=*(q.begin());q.erase(q.begin());
			if(b[i]>=0) ans+=b[i];
		}
		end:
		printf("%lld\n",ans);
		return ;
	}
	inline void mian(){if(!T) read(T);while(T--) solve();}
}
bool ED;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	auto st=clock();
	Mr_Az::mian();
	auto ed=clock();
 	cerr<<endl;
 	cerr<<"Time: "<<ed-st<<" ms\n";
 	cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
	return 0;
}

Compilation message (stderr)

feast.cpp: In function 'void Mr_Az::solve()':
feast.cpp:46:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   46 |                 for(rint i=1;i<=n;i++) read(a[i]);a[0]=-1;
      |                          ^
feast.cpp:47:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   47 |                 for(rint i=1;i<=n;i++){
      |                          ^
feast.cpp:56:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   56 |                 for(rint i=1;i<=m;i++){
      |                          ^

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29