【Codeforces 650B】Image Preview

  显然O(n)的时间扫左右端点即可。但是要考虑到先向右翻再向左翻和先向左翻再向右翻答案是不一样的。顺利地被Hack了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=500010;

char readchar() {char ch;while ((ch=getchar())!='w' && ch!='h');return ch;}

LL c[maxn],cost1;
char ch[maxn];
int n,a,b,T,ans;

int main()
{
	scanf("%d%d%d%d",&n,&a,&b,&T);
	for (int i=1;i<=n;i++) ch[i]=readchar();
	for (int i=1;i<=n;i++) c[i]=((ch[i]=='h')?1:b+1);
	if (c[1]>T) {puts("0");return 0;}
	
	LL res=c[1];
	int l=1,r=n+1;
	while (l<n && res+a+c[l+1]<=T) res+=a+c[++l];
	while (r>=2)
	{
		if (l==r) res-=c[l--]+a;
		while (l>1 && res>T) res-=c[l--]+a;
		if (res>T) break;
		if (l+(n-r+1)>ans) ans=l+(n-r+1);
		res+=c[--r]+a*2;
	}
	
	res=c[1],l=1,r=n+1;
	while (r>1 && res+a+c[r-1]<=T) res+=a+c[--r];
	while (l<=n)
	{
		if (l==r) res-=c[r++]+a;
		while (r<=n && res>T) res-=c[r++]+a;
		if (res>T) break;
		if (l+(n-r+1)>ans) ans=l+(n-r+1);
		res+=c[++l]+a*2;
	}
	printf("%d\n",ans);
	return 0;
}