记录编号	414495	评测结果	AAAAAAAATA
题目名称	[ZJOI 2013] 防守战线	最终得分	90
用户昵称	sxysxy	是否通过	未通过
代码语言	C++	运行时间	5.232 s
提交时间	2017-06-14 14:09:20	内存使用	77.00 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <cctype>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
  inline int read_string(char *str){
    int len = 1;char c;
    while(!isalpha(c = readc()));str[0] = c;
    while(isalpha(c = readc()))str[len++] = c;
    str[len] = 0;
    return len;
  }
};using IO::read_string; using IO::readint;
double A[10002][1002];
inline int dcmp(double x){
  static const double eps = 1e-8;
  static int retval[][2] = {{0, 1}, {-1, 0}};
  return retval[x<-eps][x>eps];
}
int n, m;
void pivot(int x, int y){
  double k = A[x][y]; A[x][y] = 1;
  for(int i = 0; i <= n; i++)A[x][i] /= k;
  for(int i = 0; i <= m; i++){
    if(i != x && (k = A[i][y])){
      A[i][0] += (i?-1:1)*k*A[x][0];
      A[i][y] = 0;
      for(int j = 1; j <= n; j++)
        A[i][j] -= k*A[x][j];
    }
  }
}
bool init_simplex(){
  for(int x = 0, y = 0; ; x = y = 0){
    for(int i = 1; i <= m; i++)
      if(dcmp(A[i][0]) < 0 && ((rand()&1) || (!x)))
        x = i;
    if(!x)return true;
    for(int i = 1; i <= n; i++)
      if(dcmp(A[x][i]) < 0 && ((rand()&1) || (!y)))
        y = i;
    if(!y)return false;
    pivot(x, y);
  }
}
double simplex(){
  if(!init_simplex())return 0;
  for(int x = 0, y = 0; ; x = y = 0){
    for(int i = 1; i <= n; i++){
      if(dcmp(A[0][i]) > 0){
        y = i; break;
      }
    }
    if(!y)return A[0][0];
    double inf = 1e15;
    for(int i = 1; i <= m; i++){
      double t = A[i][0]/A[i][y];
      if(dcmp(A[i][y]) > 0 && (!x || t < inf))
        inf = t, x = i;
    }
    if(!x)return 0;
    pivot(x, y);
  }
}
int main(){
  srand(20000410);
  freopen("zjoi13_defend.in", "r", stdin);
  freopen("zjoi13_defend.out", "w", stdout);
  n = readint(); m = readint();
  for(int i = 1; i <= n; i++)A[0][i] = -readint();
  for(int i = 1; i <= m; i++){
    int l = readint(); int r = readint(); int d = readint();
    A[i][0] = -d;
    for(int j = l; j <= r; j++)A[i][j] = -1;
  }
  printf("%.0lf\n", -simplex());
  return 0;
}