#include<bits/stdc++.h> #define FILE "read" #define MAXN 5010 #define INF 1000000000 using namespace std; struct node{int y,next,v,rel;}e[MAXN<<7]; int n,len,cnt,tot,ans,S,T,Link[MAXN<<6],A[MAXN],B[MAXN],W[MAXN],P[MAXN],L[MAXN],R[MAXN],num[MAXN<<6],hash[MAXN<<6]; int level[MAXN<<6],root[MAXN],son[MAXN<<6][2],id[MAXN][2]; queue<int> q; namespace INIT{ char buf[1<<15],*fs,*ft; inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;} inline int read(){ int x=0,f=1; char ch=getc(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();} while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();} return x*f; } }using namespace INIT; void add(int x,int y,int v){ e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;e[len].rel=len+1; e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;e[len].rel=len-1; } int find(int x){ int l=1,r=tot; while(l+1<r){ int mid=(l+r)>>1; if(hash[mid]<=x)l=mid; else r=mid; } return hash[l]==x?l:r; } int newnode(int last){ son[++cnt][0]=son[last][0]; son[cnt][1]=son[last][1]; return cnt; } void insert(int l,int r,int &root,int last,int x,int pos){ root=newnode(last); if(l==r) {add(pos,root,INF);if(last) add(last,root,INF); return;} int mid=(l+r)>>1; if(x<=mid) insert(l,mid,son[root][0],son[last][0],x,pos); else insert(mid+1,r,son[root][1],son[last][1],x,pos); if(son[root][0]) add(son[root][0],root,INF); if(son[root][1]) add(son[root][1],root,INF); } void query(int l,int r,int root,int x,int y,int pos){ if(x>r||y<l) return; if(x<=l&&y>=r) {add(root,pos,INF); return;} int mid=(l+r)>>1; if(mid>=x) query(l,mid,son[root][0],x,y,pos); if(mid+1<=y) query(mid+1,r,son[root][1],x,y,pos); } bool bfs(){ memset(level,-1,sizeof(level)); q.push(S); level[S]=0; while(!q.empty()){ int x=q.front(); q.pop(); for(int i=Link[x];i;i=e[i].next) if(level[e[i].y]<0&&e[i].v){ q.push(e[i].y); level[e[i].y]=level[x]+1; } } return level[T]>=0; } int MAXFLOW(int x,int flow){ if(x==T) return flow; int maxflow=0,d=0; for(int i=Link[x];i&&maxflow<flow;i=e[i].next) if(e[i].v&&level[e[i].y]==level[x]+1) if(d=MAXFLOW(e[i].y,min(e[i].v,flow-maxflow))){ e[i].v-=d; e[e[i].rel].v+=d; maxflow+=d; } if(!maxflow) level[x]=-1; return maxflow; } void solve(){ int d=0; while(bfs()) while(d=MAXFLOW(S,INF)) ans-=d; printf("%d\n",ans); } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(); for(int i=1;i<=n;++i){ A[i]=read(); B[i]=read();W[i]=read();L[i]=read();R[i]=read();P[i]=read(); num[++cnt]=A[i]; num[++cnt]=L[i]; num[++cnt]=R[i]; ans+=B[i]+W[i]; } sort(num+1,num+cnt+1); hash[++tot]=num[1]; for(int i=2;i<=cnt;++i) if(num[i]!=num[i-1]) hash[++tot]=num[i]; cnt=0; S=++cnt; T=++cnt; for(int i=1;i<=n;++i){ id[i][0]=++cnt; id[i][1]=++cnt; add(S,id[i][0],W[i]); add(id[i][0],T,B[i]); add(id[i][1],id[i][0],P[i]); query(1,tot,root[i-1],find(L[i]),find(R[i]),id[i][1]); insert(1,tot,root[i],root[i-1],find(A[i]),id[i][0]); } solve(); return 0; }
|