Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 809  Solved: 417

[][][]

Description

Input

Output

Sample Input

3 3

2 3 4

1 1 2 2

1 2 3 5

1 3 3 2

Sample Output

14

HINT

Source

 

这题是来搞笑的么？？

除了多循环几次之外和原版有啥区别？qwq、

#include
     
      #include
      
       #include
       
        #define LL long long using namespace std;const int MAXN = 51, INF = 1e9 + 10;const double eps = 1e-8;inline int read() {    char c = getchar();int x = 0,f = 1;    while(c < '0' || c > '9'){
   if(c == '-')f = -1;c = getchar();}    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}    return x * f;}int N, M;LL a[10001][1001];void Pivot(int l, int e) {    double t = a[l][e]; a[l][e] = 1;    for(int i = 0; i <= N; i++) a[l][i] /= t;    for(int i = 0; i <= M; i++) {        if(i != l && abs(a[i][e]) > eps) {            t = a[i][e]; a[i][e] = 0;            for(int j = 0; j <= N; j++)                a[i][j] -= a[l][j] * t;        }    }}bool simplex() {    while(1) {        int l = 0, e = 0; double mn = INF;        for(int i = 1; i <= N; i++)            if(a[0][i] > eps)                 {e = i; break;}        if(!e) break;        for(int i = 1; i <= M; i++)            if(a[i][e] > eps && a[i][0] / a[i][e] < mn)                mn = a[i][0] / a[i][e], l = i;        Pivot(l, e);    }    return 1;}int main() {//    freopen("a.in", "r", stdin);    srand(19260817);    N = read(); M = read();    for(int i = 1; i <= N; i++) a[0][i] = read();        for(int i = 1; i <= M; i++) {         int K = read();        while(K--) {            int S = read(), T = read();            for(int j = S; j <= T; j++)                    a[i][j] = 1;                }        int C = read();        a[i][0] = C;    }    simplex();    printf("%lld", -a[0][0]);    return 0;}