记录编号 |
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;
}