记录编号	304414	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]观光公交	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	1.029 s
提交时间	2016-09-08 14:12:22	内存使用	0.93 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;


#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0;
	while(not is_num(tmp)) tmp = getchar();
	while(    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	return res;
}


int n, m, k;
int d[maxn];
int stop_beg[maxn];
int stop_num[maxn];
int t[maxn];
int p_to[maxm], p_t[maxm];


inline void read() {
	n = get_num();
	m = get_num();
	k = get_num();

	for(int i = 1; i <= n - 1; i++) d[i] = get_num();
	
	int p_fr;
	for(int i = 1; i <= m; i++) {
		p_t[i] = get_num();
		p_fr = get_num();
		p_to[i] = get_num();
		
		stop_num[p_to[i]]++;
		stop_beg[p_fr] = max(stop_beg[p_fr], p_t[i]);
	}
}


inline void solve() {
	int now_max, now_pos, ans = 0;
	
	while(k--) {
		now_max = 0, now_pos = 0;
		for(int i = 1; i <= n; i++)  t[i] = max(t[i - 1], stop_beg[i - 1]) + d[i - 1];

		int now = 0;
		for(int i = n; i >= 1; i--) {
			if(d[i] and now and now > now_max) now_max = now, now_pos = i;
			
			if(stop_beg[i] < t[i]) now += stop_num[i];
			else now = stop_num[i];
		}
		
		if(now_max == 0) break;
		d[now_pos]--;
	}
	
	for(int i = 1; i <= n; i++) t[i] = max(t[i - 1], stop_beg[i - 1]) + d[i - 1];
	for(int i = 1; i <= m; i++) ans += t[p_to[i]] - p_t[i];
	printf("%d\n", ans);
}


int main() {
	freopen("bus.in", "r", stdin);
	freopen("bus.out", "w", stdout);
	read();
	solve();
	return 0;
}