记录编号	494740	评测结果	AAAAAAAAAA
题目名称	[NOI 2011]NOI嘉年华	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.012 s
提交时间	2018-04-13 13:24:45	内存使用	2.58 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define inf (int)1e9
using namespace std;
const int maxn=410;
struct poi{int L,R;}p[maxn];
int n,top,stack[maxn*2],g[maxn][maxn],num[maxn][maxn],pre[maxn][maxn],suf[maxn][maxn];
int main(){
	freopen("noi2011_show.in","r",stdin);
	freopen("noi2011_show.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&p[i].L,&p[i].R);
		p[i].R+=p[i].L;
		stack[++top]=p[i].L,stack[++top]=p[i].R;
	}
	sort(stack+1,stack+1+top);
	top=unique(stack+1,stack+1+top)-stack-1;
	for(int i=1;i<=n;i++){
		p[i].L=lower_bound(stack+1,stack+1+top,p[i].L)-stack;
		p[i].R=lower_bound(stack+1,stack+1+top,p[i].R)-stack;
	}
	for(int i=1;i<=top;i++){//预处理num[i][i]~num[i][top]
		for(int j=1;j<=n;j++)
			if(p[j].L>=i)num[i][p[j].R]++;
		for(int j=i+1;j<=top;j++)num[i][j]+=num[i][j-1];
	}
	for(int i=0;i<=top;i++)for(int j=0;j<=n;j++)pre[i][j]=suf[i][j]=-inf;
	pre[1][0]=0,suf[top][0]=0;
	for(int i=1;i<=top;i++){
		for(int j=0;j<=n;j++){
			if(pre[i][j]>-1)
				pre[i][pre[i][j]]=max(pre[i][pre[i][j]],j);
		}
		for(int j=n-1;j>=0;j--)pre[i][j]=max(pre[i][j],pre[i][j+1]);
		for(int j=0;j<=n;j++)
			for(int k=i+1;k<=top;k++)
				if(pre[i][j]>-1)
					pre[k][pre[i][j]]=max(pre[k][pre[i][j]],j+num[i][k]);
	}
	for(int i=top;i>=1;i--){
		for(int j=0;j<=n;j++)
			if(suf[i][j]>-1)
				suf[i][suf[i][j]]=max(suf[i][suf[i][j]],j);
		for(int j=n-1;j>=0;j--)suf[i][j]=max(suf[i][j],suf[i][j+1]);
		for(int j=0;j<=n;j++)
			for(int k=i-1;k>=1;k--)
				if(suf[i][j]>-1)
					suf[k][suf[i][j]]=max(suf[k][suf[i][j]],j+num[k][i]);
	}
	for(int i=1;i<=top;i++){
		for(int j=i;j<=top;j++){
			g[i][j]=0;
			for(int x=0,y=n;x<=n;x++){
				while(y>=0&&x+y>num[i][j]+pre[i][x]+suf[j][y])y--;
				if(y>=0)g[i][j]=max(g[i][j],x+y);
			}
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++)ans=max(ans,min(i,suf[1][i]));
	printf("%d\n",ans);
	for(int i=1;i<=n;i++){
		ans=0;
		for(int j=1;j<=p[i].L;j++)
			for(int k=p[i].R;k<=top;k++)
				ans=max(ans,g[j][k]);
		printf("%d\n",ans);
	}
	return 0;
}