제출 #1170706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170706		mr_az	Feast (NOI19_feast)	C++20	4 / 100	36 ms	9280 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=1,ans,cnt;
	bool f=0;
	int a[N],b[N],pre[N],nxt[N];
	bool vis[N];
	priority_queue<pii,vector<pii>,greater<pii>> q;
	priority_queue<pii> q1;
	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]);
		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--;
		// for(rint i=1;i<=m;i++) cerr<<b[i]<<" ";cerr<<endl;
		b[0]=b[m+1]=0;
		mem(vis,1);
		for(rint i=1;i<=m;i++){
			pre[i]=i-1;nxt[i]=i+1;
			if(b[i]<=0) q1.push({b[i],i});
			else q.push({b[i],i}),cnt++;
		}
		if(cnt<=k){
			for(rint i=1;i<=m;i++) ans+=(b[i]>0)*b[i];
			goto end;
		}
		while(cnt>k){
			int x1=INF,i1,x2=-INF,i2;
			while(q.size()){
				auto tt=q.top();
				x1=tt.first,i1=tt.second;
				if(!vis[i1]) q.pop();
				else break;
			}
			while(q1.size()){
				auto tt=q1.top();
				x2=tt.first,i2=tt.second;
				if(!vis[i2]) q1.pop();
				else break;
			}
			if(x1<-x2){
				q.pop();
				cnt--;
				b[i1]=b[pre[i1]]+x1+b[nxt[i1]];
				if(b[pre[i1]]>0) cnt--;
				if(b[nxt[i1]]>0) cnt--;
				if(b[i1]<=0) q1.push({b[i1],i1});
				else q.push({b[i1],i1}),cnt++;
				// cerr<<"com1 "<<pre[i1]<<" "<<i1<<" "<<nxt[i1]<<" "<<b[i1]<<" "<<cnt<<endl;
				vis[pre[i1]]=vis[nxt[i1]]=0;
				int pr=pre[pre[i1]],nx=nxt[nxt[i1]];
				nxt[pr]=i1;
				pre[i1]=pr;
				pre[nx]=i1;
				nxt[i1]=nx;
			}
			else{
				q1.pop();
				b[i2]=-inf;
				if(b[pre[i2]]>0) cnt--;
				if(b[nxt[i2]]>0) cnt--;
				if(b[i2]<=0) q1.push({b[i2],i2});
				else q.push({b[i2],i2}),cnt++;
				// cerr<<"com2 "<<pre[i2]<<" "<<i2<<" "<<nxt[i2]<<" "<<b[i2]<<" "<<cnt<<endl;
				vis[pre[i2]]=vis[nxt[i2]]=0;
				int pr=pre[pre[i2]],nx=nxt[nxt[i2]];
				nxt[pr]=i2;
				pre[i2]=pr;
				pre[nx]=i2;
				nxt[i2]=nx;
			}
		}
		while(q.size()) ans+=vis[q.top().second]*q.top().first,q.pop();
		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;
}

컴파일 시 표준 에러 (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]);
      |                          ^
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:58:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   58 |                 for(rint i=1;i<=m;i++){
      |                          ^
feast.cpp:64:34: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   64 |                         for(rint i=1;i<=m;i++) ans+=(b[i]>0)*b[i];
      |                                  ^

• Subtask 1: 4 / 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