#include <bits/stdc++.h>
#define va first
#define vb second
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
const int MN = 2e5+5;
const int MOD = 1e9+7;
const int INF = 1e9;
int N,A[MN],X[MN],Y[MN],C[MN],T[MN];
ll L[MN],R[MN];
vector<int> V[MN];
void upt(int s, int e, int x, int v, int i)
{
int m = (s+e)/2;
if(s==e){
T[i] = v;
return;
}
if(x<=m) upt(s,m,x,v,i<<1);
else upt(m+1,e,x,v,i<<1|1);
T[i] = A[T[i<<1]]>A[T[i<<1|1]] ? T[i<<1] : T[i<<1|1];
}
int getm(int s, int e, int x, int y, int i)
{
if(e<x||y<s) return 0;
if(x<=s&&e<=y) return T[i];
int m = (s+e)/2;
int l = getm(s,m,x,y,i<<1), r = getm(m+1,e,x,y,i<<1|1);
return A[l]>A[r] ? l : r;
}
int maxc(int x, int y)
{
int res = 0;
for(int i:V[x]){
if(Y[i]>y) continue;
res = max(res,C[i]);
}
return res;
}
ll solve(int s, int e, int y)
{
if(s<1||e>N||s>e) return 0;
//cout << s << ' ' << e << ' ' << y << '\n';
int m = getm(1,N,s,e,1);
if(L[m]<0) L[m] = solve(s,m-1,A[m]);
if(R[m]<0) R[m] = solve(m+1,e,A[m]);
ll res = L[m]+R[m]+maxc(m,y);
res = max(res,solve(s,m-1,y)+R[m]);
res = max(res,L[m]+solve(m+1,e,y));
return res;
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> N;
for(int i=1; i<=N; i++){
cin >> A[i];
upt(1,N,i,i,1);
L[i] = R[i] = -1;
}
A[0] = -1;
int M;
cin >> M;
ll sum = 0;
for(int i=0; i<M; i++){
cin >> X[i] >> Y[i] >> C[i];
V[X[i]].push_back(i);
sum += C[i];
}
cout << sum-solve(1,N,N);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5104 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 12 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 13 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 16 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 18 |
Correct |
11 ms |
5120 KB |
Output is correct |
| 19 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 20 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 21 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 22 |
Correct |
5 ms |
5120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5104 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 12 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 13 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 16 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 18 |
Correct |
11 ms |
5120 KB |
Output is correct |
| 19 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 20 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 21 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 22 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 23 |
Correct |
10 ms |
5224 KB |
Output is correct |
| 24 |
Correct |
10 ms |
5280 KB |
Output is correct |
| 25 |
Correct |
10 ms |
5248 KB |
Output is correct |
| 26 |
Correct |
11 ms |
5248 KB |
Output is correct |
| 27 |
Correct |
10 ms |
5248 KB |
Output is correct |
| 28 |
Correct |
9 ms |
5248 KB |
Output is correct |
| 29 |
Correct |
11 ms |
5248 KB |
Output is correct |
| 30 |
Correct |
14 ms |
5248 KB |
Output is correct |
| 31 |
Correct |
13 ms |
5248 KB |
Output is correct |
| 32 |
Correct |
302 ms |
5496 KB |
Output is correct |
| 33 |
Correct |
226 ms |
5248 KB |
Output is correct |
| 34 |
Correct |
193 ms |
5368 KB |
Output is correct |
| 35 |
Correct |
148 ms |
5248 KB |
Output is correct |
| 36 |
Correct |
248 ms |
5376 KB |
Output is correct |
| 37 |
Correct |
257 ms |
5368 KB |
Output is correct |
| 38 |
Correct |
311 ms |
5496 KB |
Output is correct |
| 39 |
Correct |
13 ms |
5376 KB |
Output is correct |
| 40 |
Correct |
362 ms |
5388 KB |
Output is correct |
| 41 |
Correct |
17 ms |
5248 KB |
Output is correct |
| 42 |
Correct |
13 ms |
5248 KB |
Output is correct |
| 43 |
Correct |
367 ms |
5400 KB |
Output is correct |
| 44 |
Correct |
14 ms |
5248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5104 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 12 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 13 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 16 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 18 |
Correct |
11 ms |
5120 KB |
Output is correct |
| 19 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 20 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 21 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 22 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 23 |
Correct |
10 ms |
5224 KB |
Output is correct |
| 24 |
Correct |
10 ms |
5280 KB |
Output is correct |
| 25 |
Correct |
10 ms |
5248 KB |
Output is correct |
| 26 |
Correct |
11 ms |
5248 KB |
Output is correct |
| 27 |
Correct |
10 ms |
5248 KB |
Output is correct |
| 28 |
Correct |
9 ms |
5248 KB |
Output is correct |
| 29 |
Correct |
11 ms |
5248 KB |
Output is correct |
| 30 |
Correct |
14 ms |
5248 KB |
Output is correct |
| 31 |
Correct |
13 ms |
5248 KB |
Output is correct |
| 32 |
Correct |
302 ms |
5496 KB |
Output is correct |
| 33 |
Correct |
226 ms |
5248 KB |
Output is correct |
| 34 |
Correct |
193 ms |
5368 KB |
Output is correct |
| 35 |
Correct |
148 ms |
5248 KB |
Output is correct |
| 36 |
Correct |
248 ms |
5376 KB |
Output is correct |
| 37 |
Correct |
257 ms |
5368 KB |
Output is correct |
| 38 |
Correct |
311 ms |
5496 KB |
Output is correct |
| 39 |
Correct |
13 ms |
5376 KB |
Output is correct |
| 40 |
Correct |
362 ms |
5388 KB |
Output is correct |
| 41 |
Correct |
17 ms |
5248 KB |
Output is correct |
| 42 |
Correct |
13 ms |
5248 KB |
Output is correct |
| 43 |
Correct |
367 ms |
5400 KB |
Output is correct |
| 44 |
Correct |
14 ms |
5248 KB |
Output is correct |
| 45 |
Runtime error |
191 ms |
37624 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 46 |
Halted |
0 ms |
0 KB |
- |
