比赛 |
20110729 |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
最后的利益 |
最终得分 |
100 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-29 08:55:15 |
显示代码纯文本
#include <cstdio>
#include <set>
#include <map>
using namespace std;
const int MAXN=50005;
struct Node
{
int v;
Node *next;
void *operator new (size_t,void *p){return p;}
Node(){}
Node(int _v,Node *_next):v(_v),next(_next){}
}*adj[MAXN],pool[MAXN],*mem=pool;
inline void addedge(int u,int v)
{
adj[u]=new (mem++)Node(v,adj[u]);
}
set<int> hash;
map<int,int> trans,rtrans;
int N;
int L[MAXN],R[MAXN];
int d[MAXN];
int main()
{
freopen("9cwy.in","r",stdin);
freopen("9cwy.out","w",stdout);
scanf("%d",&N);
for(int i=0;i<N;i++)
{
scanf("%d%d",L+i,R+i);
if (L[i]!=R[i])
{
hash.insert(L[i]);
hash.insert(R[i]);
}
}
int tot=0;
for(set<int>::iterator it=hash.begin();it!=hash.end();it++)
{
trans[*it]=++tot;
rtrans[tot]=*it;
}
for(int i=0;i<N;i++)
{
L[i]=trans[L[i]],R[i]=trans[R[i]];
if (L[i]!=R[i])
addedge(R[i],L[i]);
}
d[0]=0;
for(int i=1;i<=tot;i++)
{
d[i]=d[i-1];
int t=0;
for(Node *p=adj[i];p;p=p->next)
if ((t=d[p->v]+rtrans[i]-rtrans[p->v])>d[i])
d[i]=t;
}
printf("%d\n",d[tot]);
return 0;
}