#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<map>
#include<random>
#include<time.h>
#include<cassert>
#include<chrono>
#include<set>
#include<unordered_set>
#include<array>
using namespace std;
#define ull unsigned long long
#define pb push_back
#define ll long long
#define all(a) a.begin(), a.end()
#define ld long double
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 2e5 + 10;
vector<pair<int, ll>> mas[N];
int a[N];
vector<pair<int, ll>> solve(int l, int r) {
if (l == r) {
return mas[l];
}
int total = 0;
for (int i = l; i <= r; i++) {
total += mas[i].size();
}
if (total == 0) {
return vector<pair<int, ll>>{};
}
int m = l;
for (int i = l + 1; i <= r; i++) {
if (a[i] > a[m]) {
m = i;
}
}
auto arr1 = solve(l, m - 1), arr2 = solve(m + 1, r);
ll best1 = 0, best2 = 0;
for (auto p : arr1) {
if (p.first <= a[m]) {
best1 = max(best1, p.second);
}
}
for (auto p : arr2) {
if (p.first <= a[m]) {
best2 = max(best2, p.second);
}
}
vector<pair<int, ll>> res;
{
int j = -1;
for (auto p : arr1) {
while (j + 1 < arr2.size() && arr2[j + 1].first <= p.first) {
j++;
}
if (p.first <= a[m]) {
res.pb({p.first, p.second + (j >= 0 ? arr2[j].second : 0ll)});
} else {
res.pb({p.first, p.second + best2});
}
}
}
{
int j = -1;
for (auto p : arr2) {
while (j + 1 < arr1.size() && arr1[j + 1].first <= p.first) {
j++;
}
if (p.first <= a[m]) {
res.pb({p.first, p.second + (j >= 0 ? arr1[j].second : 0ll)});
} else {
res.pb({p.first, p.second + best1});
}
}
}
for (auto p : mas[m]) {
res.pb({p.first, p.second + best1 + best2});
}
sort(all(res));
return res;
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int m;
cin >> m;
ll sum = 0;
for (int i = 0; i < m; i++) {
int x, y, c;
cin >> x >> y >> c;
x--;
if (y <= a[x]) continue;
sum += c;
mas[x].pb({y, c});
}
auto res = solve(0, n - 1);
ll mx = 0;
for (auto p : res) {
mx = max(mx, p.second);
}
cout << sum - mx << endl;
return 0;
}
Compilation message
constellation3.cpp: In function 'std::vector<std::pair<int, long long int> > solve(int, int)':
constellation3.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | while (j + 1 < arr2.size() && arr2[j + 1].first <= p.first) {
| ~~~~~~^~~~~~~~~~~~~
constellation3.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | while (j + 1 < arr1.size() && arr1[j + 1].first <= p.first) {
| ~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
