某島

… : "…アッカリ～ン . .. . " .. .
July 3, 2022

資料

[NOI2008] 志願者招募

const int N = int(1e4) + 9, M = int(1e3) + 9;

struct Simplex {
DB a[N][M];
int n, m;

void init(int _n,int _m) { //a矩陣m行n列
n = _n+1; m = _m+1;
}
void pivot(int in, int out) {
REP(i, m) if(i!=in) a[out][i] /= -a[out][in]; //重置out約束
a[out][in] = 1/a[out][in];

REP(i, n) if (i!=out && sgn(a[i][in])) { //重新計算其他約束
DB t = a[i][in]; a[i][in] = 0;
REP(j, m) a[i][j] += t*a[out][j];
}
}

DB run() {
while (true) {
int in=0, out=0; DB Min=OO;
REP_1(i, m) if(sgn(a[0][i])>0) {
in=i;
break;
}
if(!in)return a[0][0];
REP_1(i, n) if(sgn(a[i][in])<0&&a[i][0]/-a[i][in]<Min) {
Min=a[i][0]/-a[i][in];
out=i;
}
if(!out)throw ; //unbounded
pivot(in, out);
}
}
} fst;

int main() {

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

// z D
// C A

int n, m; RD(m, n); fst.init(n, m);

REP_1(j, m) RD(fst.a[0][j]);

REP_1(i, n) {
int l, r; RD(l, r, fst.a[i][0]);
FOR_1(j, l, r) fst.a[i][j]=-1;
}
printf("%d\n", int(fst.run()));
}