#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<queue>
#include<algorithm>
using namespace std;
#define offset 100010
struct SNode
{
int si,fi;
}node[110];
int dp[300000+10];
bool flag[300000+10];
bool cmp(const SNode a,const SNode b)
{
return a.si <b.si ;
}
int main()
{
int N;
while(scanf("%d",&N)!=EOF){
for(int i=0;i<N;i++){
scanf("%d %d",&node[i].si,&node[i].fi);
// node[i].fi +=offset;
node[i].si +=offset;
}
sort(node,node+N,cmp);
memset(dp,0,300000*sizeof(int));
memset(flag,false,sizeof(flag));
int up=0,k=0;
for(k=0;k<N && node[k].si<=offset;k++){
int si=node[k].si ,fi=node[k].fi;
if( fi<=0)continue;
for(int j=1;j<=up;j++){
if(flag[j]){
printf("-------%d %d--------\n",si-offset,fi);
int n=j+si-offset;
if( fi+dp[j]>0 || !flag[n] )
dp[n]+=fi+dp[j];
flag[n]=true;
up=max(n,up);
}
}
if( fi>0 || !flag[si] )
dp[si]+=fi;
flag[si]=true;
up=max(si,up);
}
for( ;k<N;k++){
int si=node[k].si,fi=node[k].fi ;
if(si-offset+fi<=0)continue;
printf("-------%d %d--------\n",si-offset,fi);
for(int j=up;j>0;j--){
if(flag[j]){
int n=j+si-offset;
if(fi+dp[j]>0 || !flag[n] )
dp[n]+=fi+dp[j];
printf("%d --> %d %d \n",j-offset,n-offset,dp[n]);
flag[n]=true;
up=max(n,up);
}
}
if( fi>0 || !flag[si])
dp[si]+=fi;
flag[si]=true;
up=max(si,up);
}
int ans=0;
for(int i=offset;i<=up;i++){
if(dp[i]>=0 && flag[i]){
printf("%d %d\n",i-offset,dp[i]);
ans=max(ans,i-offset+dp[i]);
}
}
printf("%d\n",ans);
}
return 0;
}
posted on 2009-07-15 21:59
iyixiang 阅读(367)
评论(0) 编辑 收藏 引用 所属分类:
fojpojzojhoj^^^^