Description：

若干条线段，每条线段会有一个优美度 $v$ 。如果线段 $L_i, L_j$ 有交， $v_i > v_j$ ，先走过了 $L_i$ ，紧接着又走过了 $ L_j$ ，那么就会获得的额外优美度 $(v_i + v_j) \times \lfloor \frac{i+j}{2} \rfloor$ ，可以走多次，最大化总优美度。

$1\leqslant n\leqslant 300$

Solution：

首先 $v_i$ 可以先直接累加起来，然后就变成 $DAG$ 上边有边权不可重复经过最大权路径覆盖问题，可以在拆点二分图中两个拆完的点连边时把边权作为费用跑最大费用最大流，因为这个流量流过代表选了这条边，就会获得价值，注意增广到负权时 $break$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

int n;

#define MAXN 2010

struct edge

{

	int to,nxt,f,c;

}e[MAXN * MAXN * 2 + (MAXN + MAXN) * 2];

int edgenum = 0;

int lin[MAXN << 1];

void add(int a,int b,int f,int c)

{//cout << a << " " << b << " " << f << " " << c << endl;

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].c =  c;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].c = -c;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int s,t;

int d[MAXN << 1],pre[MAXN << 1],rate[MAXN << 1];

bool inq[MAXN << 1];

#define INF 0x3f3f3f3f

#define NEG 0xc0c0c0c0

bool SPFA()

{

	//memset(d,0xc0,sizeof(d));

	for(int i = s; i <= t; ++i) d[i] = -INF;

	queue<int> q;q.push(s);

	d[s] = 0;rate[s] = INF;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] < d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				pre[e[i].to] = i;rate[e[i].to] = min(rate[k],e[i].f);

				if(!inq[e[i].to])

				{

					inq[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return (d[t] != -INF);

}

int flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return d[t] * rate[t];

}

int EK()

{

	int ans = 0;

	while(SPFA())

	{

		if(d[t] > 0)ans += flow();

		else break;

	}

	return ans;

}

struct point{double x,y;};

struct line

{

	point p1,p2;

	double A,B,C;

	int val;

}l[MAXN];

bool equal(double a,double b)

{

	if(fabs(a - b) <= 1e-9)return true;

	else return false;

} 

bool check(line a,line b)

{

	if(min(a.p1.x,a.p2.x) > max(b.p1.x,b.p2.x))return false;

	if(max(a.p1.x,a.p2.x) < min(b.p1.x,b.p2.x))return false;

	if(min(a.p1.y,a.p2.y) > max(b.p1.y,b.p2.y))return false;

	if(max(a.p1.y,a.p2.y) < min(b.p1.y,b.p2.y))return false;

	if(a.A == 0 && b.A == 0)

	{

		if(a.C / a.B != b.C / b.B)return false;

		else return true;

	}

	if(a.B == 0 && b.B == 0)

	{

		if(a.C / a.A != b.C / b.A)return false;

		else return true;

	}

	if(equal(a.B * b.A - a.A * b.B,0))

	{

		if(equal(a.C * b.A - a.A * b.C,0))

		{

			if(min(a.p1.x,a.p2.x) <= max(b.p1.x,b.p2.x) && max(a.p1.x,a.p2.x) >= min(b.p1.x,b.p2.x)

			 && min(a.p1.y,a.p2.y) <= max(b.p1.y,b.p2.y) && max(a.p1.y,a.p2.y) >= min(b.p1.y,b.p2.y))return true;

			else return false;

		}

		else return false;

	}

	else

	{

		point res;//cout << "$$$" << endl;

		res.x = (double)(b.C * a.B - b.B * a.C) / (a.A * b.B - b.A * a.B);

		res.y = (double)(b.A * a.C - a.A * b.C) / (a.A * b.B - b.A * a.B);//cout << res.x << " " << res.y << endl;

		if(min(a.p1.x,a.p2.x) <= res.x && res.x <= max(a.p1.x,a.p2.x) && min(a.p1.y,a.p2.y) <= res.y && res.y <= max(a.p1.y,a.p2.y))

		{

			if(min(b.p1.x,b.p2.x) <= res.x && res.x <= max(b.p1.x,b.p2.x) && min(b.p1.y,b.p2.y) <= res.y && res.y <= max(b.p1.y,b.p2.y))

				return true;

			else return false;

		}

		else return false;

	}

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	int sum = 0; 

	for(int i = 1;i <= n;++i)

	{

		scanf("%lf%lf%lf%lf%d",&l[i].p1.x,&l[i].p1.y,&l[i].p2.x,&l[i].p2.y,&l[i].val);

		l[i].A = l[i].p2.y - l[i].p1.y;l[i].B = l[i].p1.x - l[i].p2.x;

		l[i].C = l[i].p1.x * (l[i].p1.y - l[i].p2.y) + l[i].p1.y * (l[i].p2.x - l[i].p1.x);

		sum += l[i].val;

	}

	s = 0;t = 2 * n + 1;

	for(int i = 1;i <= n;++i)

	{

		add(s,i,1,0);

		add(i+n,t,1,0);

		for(int j = 1;j <= n;++j)

		{

			if(l[i].val > l[j].val && check(l[j],l[i]))

				add(i,j + n,1,(l[i].val + l[j].val) * ((i + j) / 2));

		}

	}

	cout << EK() + sum << endl;

	return 0;

}