[bzoj 3112][zjoi 2013] 防守战线

#include <cfloat>
#include <algorithm>
const int MAXN = 1005;
const int MAXM = 10005;
const double EPS = 1e-7;
struct  {
  double A[MAXN][MAXM], b[MAXN], c[MAXM], v;
  int n, m;
   void pivot(int l, int e) {
       b[l] /= A[l][e];
     for (int i = 1; i <= m; i++) if (i != e) A[l][i] /= A[l][e];
       A[l][e] = 1 / A[l][e];
       for (int i = 1; i <= n; i++) {
          if (i != l && abs(A[i][e]) > EPS) {
                b[i] -= A[i][e] * b[l];
              for (int j = 1; j <= m; j++) if (j != e) A[i][j] -= A[i][e] * A[l][j];
             A[i][e] = -A[i][e] * A[l][e];
            }
        }
        v += c[e] * b[l];
        for (int i = 1; i <= m; i++) if (i != e) c[i] -= c[e] * A[l][i];
       c[e] = -c[e] * A[l][e];
  }
    double operator()(int n, int m) {
        this->n = n;
     this->m = m;
     while (true) {
         int i;
          for (i = 1; i <= m; i++) if (c[i] > EPS) break;
         int e = i;
          if (e == m + 1) return v;
          double temp = DBL_MAX;
          int l;
          for (i = 1; i <= n; i++) if (A[i][e] > EPS && b[i] / A[i][e] < temp) temp = b[i] / A[i][e], l = i;
            if (temp == DBL_MAX) return DBL_MAX;
           pivot(l, e);
     }
    }
} lp;
int main() {
   int n, m;
   scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lf", &lp.b[i]);
  for (int i = 1; i <= m; i++) {
      int l, r, d;
        scanf("%d %d %d", &l, &r, &d);
     for (int j = l; j <= r; j++) lp.A[j][i] = 1;
        lp.c[i] = d;
 }
    printf("%lldn", (long long) (lp(n, m) + 0.5));
   return 0;
}