记录编号	402008	评测结果	AAAAAAAAAA
题目名称	[NOI 2008]志愿者招募	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.424 s
提交时间	2017-05-04 20:03:37	内存使用	31.02 MiB

#include<cmath>
#include<cstdio>
#define EPS 1e-10
#define INF 1e10
#define MAXM 10010
#define MAXN 1010
using namespace std;
namespace IO{
	char buf[1<<15],*fs,*ft;
	inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int qr(){
		int x=0,rev=0,ch=gc();
		while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=gc();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
		return rev?-x:x;}
}using namespace IO;
/*******************************************************************************************************/
int N,M;
double ans=0,c[MAXN],a[MAXM][MAXN],b[MAXM];
void Pivot(int l,int e){
	b[l]/=a[l][e];
	for(int i=1;i<=N;i++){if(i!=e){a[l][i]/=a[l][e];}}
	a[l][e]=1.0/a[l][e];
	for(int i=1;i<=M;i++){
		if(i!=l&&fabs(a[i][e])>EPS){
			b[i]-=a[i][e]*b[l];
			for(int j=1;j<=N;j++){if(j!=e){a[i][j]-=a[i][e]*a[l][j];}}
			a[i][e]=-a[i][e]*a[l][e];}}
	ans+=c[e]*b[l];
	for(int i=1;i<=N;i++){if(i!=e){c[i]-=a[l][i]*c[e];}}
	c[e]=-c[e]*a[l][e];}
double Simplex(){
	int j,l,e;
	double ret;
	while(1){
		for(j=1;j<=N;j++){if(c[j]>EPS)break;}
		if(j==N+1)return ans;
		e=j;ret=INF;
		for(int i=1;i<=M;i++){
			if(a[i][e]>EPS&&ret>b[i]/a[i][e]){
				ret=b[i]/a[i][e];l=i;}}
		if(ret==INF)return INF;
		Pivot(l,e);}
	return INF;}
int sb(){
	freopen("employee.in","r",stdin);
	freopen("employee.out","w",stdout);
	N=qr();M=qr();
	int s,t;
	for(int i=1;i<=N;i++){c[i]=qr()*1.0;}
	for(int i=1;i<=M;i++){
		s=qr();t=qr();b[i]=qr()*1.0;
		for(int j=s;j<=t;j++){
			a[i][j]=1;}}
	printf("%d",(int)Simplex());
	return 0;}
int chh=sb();
int main(){;}