lp3615 如厕计划

观察题面我们可以发现，如果男性比女性多的话，显然是无法符合要求的；否则，女性使用男女通用单间的个数不应该超过男女性的人数差。
我们不妨把部分的男女性人数差个女性视为男性——这是一种贪心的做法。于是就把女性多于男性的情况归约成了男性和女性相同的情况。
在这种情况下，任何时候都不应该有女性进入男女通用单间。这也就意味着，如果令男性为1，女性为-1，那么在任何时候，数列的前缀和都应该保证为大于等于-1。
然而，要保证一个前缀和始终大于某个数是很难维护的——这是因为位于后面的信息我们无法得到。我们考虑维护后缀和，这样就可以预先得到位于后面的信息了。
于是，我们考虑对每一段计算它的贡献。

#include<iostream>
#include<cstdio>
#include<cstring>

inline long long Max(long long A,long long B){
	return A>B?A:B;
}
inline long long Min(long long A,long long B){
	return A<B?A:B;
}

long long n,m;
int len;
char ch[200005];
long long dlt=0,a[200005],mx[200005],l[200005];
void init(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		len=strlen(ch+1);
		scanf("%lld",&l[i]);
		for(int j=len;j>=1;--j){
			a[i]+=(ch[j]=='M'?1:-1); 
			mx[i]=Max(mx[i],a[i]);
		}
		dlt+=a[i]*l[i];
	}
	if(dlt>0){
		puts("-1");
		return ;
	}
	long long nw=0,ans=1;
	for(int i=m;i>=1;--i){
		if(a[i]>0){
			ans=Max(ans,(l[i]-1)*a[i]+nw+mx[i]);
		}else{
			ans=Max(ans,nw+mx[i]);
		}
		nw+=l[i]*a[i];
	}
	printf("%lld",ans-1);
}

int main(){
	freopen("queue.in","r",stdin);
	freopen("queue.out","w",stdout);
	init();
	return 0;
}