#include <bits/stdc++.h>
#define int ll
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
cerr << to_string(h);
if(sizeof ...(t)) cerr << ", ";
DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif
const int INF = 1e9 + 7, N = 1e6 + 7;
int p[N], q[N];
ll a[N], b[N], s[N], t[N];
V<pi> G[N];
signed main()
{
IO_OP;
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> s[i] >> p[i];
a[i] += a[i - 1];
}
for(int i = 1; i <= m; i++) {
cin >> b[i] >> t[i] >> q[i];
b[i] += b[i - 1];
}
ll ans = 0;
for(int i = 1; i <= n; i++) {
/*
a[i] + b[j] <= s[i]
b[j] <= s[i] - a[i]
*/
int j = int(upper_bound(b, b + m + 1, s[i] - a[i]) - b);
if(!j) continue;
// if(i-th a before j-th b) ans += p[i]
G[i].EB(j, p[i]);
}
for(int j = 1; j <= m; j++) {
/*
a[i] + b[j] <= t[j]
a[i] <= t[j] - b[j]
*/
int i = int(upper_bound(a, a + n + 1, t[j] - b[j]) - a);
if(!i) continue;
// original: if(j-th b before i-th a) ans += q[j]
ans += q[j];
// now: if(i-th a before j-th b) ans += -q[j]
G[i].EB(j, -q[j]);
}
map<int, ll> mp;
for(int i = 1; i <= n; i++) {
sort(ALL(G[i]), greater<pi>());
for(auto [j, v] : G[i]) {
// 0 ~ j - 1 add v
ans += v;
if(j > m) continue;
mp[j] -= v;
if(mp[j] < 0) {
auto it = mp.find(j);
assert(it -> S < 0);
while(it -> S < 0) {
it++;
if(it != mp.end()) {
mp[it -> F] += mp[prev(it) -> F];
mp.erase(prev(it));
} else {
mp.erase(prev(it));
break;
}
}
}
}
}
for(auto [x, y]:mp) {
ans += y;
assert(y >= 0);
}
cout << ans << '\n';
}
Compilation message
dishes.cpp: In function 'int main()':
dishes.cpp:77:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | for(auto [j, v] : G[i]) {
| ^
dishes.cpp:98:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
98 | for(auto [x, y]:mp) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
438 ms |
54220 KB |
Output is correct |
| 2 |
Incorrect |
241 ms |
43736 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
438 ms |
54220 KB |
Output is correct |
| 2 |
Incorrect |
241 ms |
43736 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
438 ms |
54220 KB |
Output is correct |
| 2 |
Incorrect |
241 ms |
43736 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
