【Codeforces 632E】Thief in a Shop
【Codeforces 650C】Table Compression

【Codeforces 650B】Image Preview

Zarxdy34 posted @ 2016年3月08日 19:36 in Codeforces with tags 坑题 , 356 阅读

  显然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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Back to Top