#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll
const int BINF = 1e18;
const int N = 2e5 + 10;
int h[N], all[N], dp[N], dp2[N];
vector<pair<int, int>> have[N];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
h[i] = n - h[i];
}
int m;
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y, c;
cin >> x >> y >> c;
have[x].pb({n - y + 1, c});
all[x] += c;
}
for (int i = 1; i <= n; i++) {
dp[i] = BINF;
}
for (int i = 1; i <= n; i++) {
int mn = BINF;
for (int j = h[i] + 1; j <= n; j++) {
mn = min(mn, dp[j]);
dp[j] = BINF;
}
dp[n + 1] = min(dp[n + 1], mn);
if (!have[i].empty()) {
for (int j = 1; j <= n + 1; j++) {
dp2[j] = min(BINF, dp[j] + all[i]);
}
for (auto it : have[i]) {
if (it.F > h[i - 1]) {
for (int j = 1; j <= n + 1; j++) {
dp2[min(j, it.F)] = min(dp2[min(j, it.F)], dp[j] + all[i] - it.S);
}
}
else {
dp2[it.F] = min(dp2[it.F], dp[n + 1] + all[i] - it.S);
}
}
for (int j = 1; j <= n + 1; j++) {
dp[j] = dp2[j];
}
}
}
int ans = BINF;
for (int i = 1; i <= n + 1; i++) {
ans = min(ans, dp[i]);
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
