• 个人简介

    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
    #include <stdio.h>
    #include <string.h> 
    #include <algorithm>
    #include <queue>
    #define od(x) printf("%d",x)
    #define odb(x) printf("%d ",x)
    #define odl(x) printf("%d\n",x)
    #define odp(x,y) printf("%d %d\n",x,y)
    #define ol(x) puts("")
    #define old(x) printf("%lld",x)
    #define oldb(x) printf("%lld ",x)
    #define oldl(x) printf("%lld\n",x)
    #define oldp(x,y) printf("%lld %lld\n",x,y)
    #define rg(x) for(int i=1;i<=(x);i++){
    #define gr }
    #define rrg(x) for(int i=0;i<(x);i++)
    #define rdln(a) a[i]=read();
    #define rdln0(a,x) rrg(x) rdln(a) gr
    #define rdln1(a,x) rg(x) rdln(a) gr
    //#define int long long
    inline int read()
    {
    	int num=0,f=1;char c=getchar();
    	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    	while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    	return num*f;
    }
    inline int min(int a,int b){return a>b?b:a;}
    inline int max(int a,int b){return a<b?b:a;}
    struct Edge{
    	int v,w,nxt,c;
    }e[200005];
    int h[200005],cnt=2;
    inline void addedge(int u,int v,int w,int c)
    {
    	e[cnt]=(Edge){v,w,h[u],c};
    	h[u]=cnt++;
    }
    int dis[100005],cur[100005],inq[100005];
    inline bool devin(int s,int t)
    {
    	memset(dis,0x3f,sizeof(dis));
    	memcpy(cur,h,sizeof(cur));
    	int inf=dis[0];
    	std::queue<int>q;
    	q.push(s);dis[s]=0;
    	while(!q.empty())
    	{
    		int u=q.front();q.pop();
    		inq[u]=0;
    		for(int i=h[u];i;i=e[i].nxt)
    		{
    			int v=e[i].v;
    			if(e[i].w&&dis[v]>dis[u]+e[i].c)
    			{
    				dis[v]=dis[u]+e[i].c;
    				if(!inq[v])
    				{
    					inq[v]=1;
    					q.push(v);
    				}
    			}
    		}
    	}
    	return dis[t]!=inf;
    }
    #define vis inq
    int dfs(int u,int t,int flow,int& cost)
    {
    	if(u==t)return flow;
    	vis[u]=1;
    	int ans=0;
    	for(int& i=cur[u];i&&ans<flow;i=e[i].nxt)
    	{
    		int v=e[i].v;
    		if(!vis[v]&&e[i].w&&dis[v]==dis[u]+e[i].c)
    		{
    			int fl=dfs(v,t,min(e[i].w,flow-ans),cost);
    			if(fl)cost+=fl*e[i].c,e[i].w-=fl,e[i^1].w+=fl,ans+=fl;
    		}
    	}
    	vis[u]=0;
    	return ans;
    }
    int n=read();
    int s=0,t=30000;
    inline void add(int u,int v,int w,int c)
    {//odp(u,v);
    	addedge(u,v,w,-c);
    	addedge(v,u,0,c);
    }
    void build(int o,int l,int r)
    {
    	if(l==r)
    	{
    		add(o+n,t,1,0);
    		return;
    	}
    	int m=l+r>>1;
    	build(o<<1,l,m);
    	build(o<<1|1,m+1,r);
    	add(n+o,n+(o<<1),m-l+1,0);
    	add(n+o,n+(o<<1|1),r-m,0);
    }
    void add(int o,int l,int r,int L,int R,int v)
    {
    	if(L<=l&&r<=R)
    	{
    		add(v,o+n,1,0);
    		return;
    	}
    	int m=l+r>>1;
    	if(L<=m)add(o<<1,l,m,L,R,v);
    	if(m<R)add(o<<1|1,m+1,r,L,R,v);
    }
    signed main()
    {
    	build(1,1,5000);
    	rg(n)int l=read(),r=read()-1,w=read();
    	add(s,i,1,w);add(1,1,5000,l,r,i);gr;
    /*	int n=read(),m=read(),s=read(),t=read(),flow=0,mincost=0,x;
    	while(m--)
    	{
    		int u=read(),v=read(),w=read(),c=read();
    		addedge(u,v,w,c);
    		addedge(v,u,0,-c);
    	}*/
    	int x,mincost=0,flow=0;
    	while(devin(s,t))while(x=dfs(s,t,0x3f3f3f3f,mincost))flow-=x;
    	printf("%d\n",-mincost);
    }
    
  • 通过的题目

  • 最近活动

  • 最近编写的题解

    This person is lazy and didn't write any solutions.
  • Stat

  • Rating

题目标签

implementation
3
2021
2
binary search
2
data structures
2
dp
2
greedy
2
sortings
2
退群杯
2
NOI
2
constructive algorithms
1
*2500
1
two pointers
1
*1600
1
*1200
1
strings
1
*800
1
系统测试
1