#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//===================//
// Added libraries //
//===================//
//===================//
//end added libraries//
//===================//
void program();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
program();
}
//===================//
// begin program //
//===================//
const int MX = 3000;
int n, a[MX], m, x[MX], y[MX], c[MX];
int SA[MX];
ll SEGMAX[MX*4];
ll dp[MX][MX];
vi stars[MX];
void buildSeg(int p=0, int l=0, int r=n) {
if(l == r) {
SEGMAX[p] = a[l];
return;
}
int m=(l+r)/2;
buildSeg(p*2+1,l,m);
buildSeg(p*2+2,m+1,r);
SEGMAX[p] = max(SEGMAX[p*2+1], SEGMAX[p*2+2]);
}
int getMax(int i, int j, int p=0, int l=0, int r=n) {
if(j < l || i > r) return 0;
if(i <= l && j >= r) return SEGMAX[p];
int m=(l+r)/2;
int a=getMax(i,j,p*2+1,l,m);
int b=getMax(i,j,p*2+2,m+1,r);
return max(a,b);
}
ll getAns(int i, int last) {
if(i == -1) return 0;
if(dp[i][last] == -1) {
dp[i][last] = getAns(i-1,last);
for(int u:stars[i]) {
if(y[u] >= last) continue;
dp[i][last] = max(dp[i][last], c[u]+getAns(i-1,u));
}
}
return dp[i][last];
}
void program() {
cin>>n;
RE(i,n) cin>>a[i];
a[n] = n;
cin>>m;
RE(i,m) cin>>x[i]>>y[i]>>c[i], x[i]--;
RE(i,m) stars[x[i]].pb(i);
buildSeg();
RE(i,MX) RE(j,MX) dp[i][j] = -1;
ll tot=0;
RE(i,m) tot+=c[i];
cout<<tot-getAns(n-1,0)<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
70904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
70904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
70904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
