#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
int n, m;
ll a[maxn], s[maxn], p[maxn];
ll b[maxn], t[maxn], q[maxn];
ll pref[2][maxn];
void input()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> a[i] >> s[i] >> p[i];
for (int i = 1; i <= m; i ++)
cin >> b[i] >> t[i] >> q[i];
}
void prefix_sums()
{
for (int i = 1; i <= n; i ++)
{
pref[0][i] = pref[0][i - 1] + a[i];
}
for (int i = 1; i <= m; i ++)
{
pref[1][i] = pref[1][i - 1] + b[i];
}
}
ll dp[maxn];
vector < pair < int, ll > > upd[maxn];
int X[maxn], Y[maxn];
const ll inf = 1e18;
void dynamic()
{
for (int i = 1; i <= n; i ++)
{
ll free_time = s[i] - pref[0][i];
while(X[i] <= m && pref[1][X[i]] <= free_time)
X[i] ++;
X[i] --;
upd[i - 1].push_back({X[i] + 1, - p[i]});
///cout << "point " << i - 1 << " " << X[i] + 1 << " " << -p[i] << endl;
}
for (int i = 1; i <= m; i ++)
{
ll free_time = t[i] - pref[1][i];
while(Y[i] <= m && pref[0][Y[i]] <= free_time)
Y[i] ++;
Y[i] --;
if (Y[i] >= 0)
{
upd[Y[i]].push_back({i, q[i]});
//cout << "point " << Y[i] << " " << i << " " << q[i] << endl;
}
}
for (int j = 0; j <= m; j ++)
dp[j] = 0;
for (int i = 1; i <= n; i ++)
{
sort(upd[i].begin(), upd[i].end());
for (pair < int, ll > cur : upd[i - 1])
{
for (int d = cur.first; d <= m; d ++)
{
dp[d] += cur.second;
}
}
for (int j = 1; j <= m; j ++)
{
dp[j] = max(dp[j], dp[j - 1]);
}
/**cout << "state " << i << endl;
for (int j = 0; j <= m; j ++)
cout << dp[j] << " ";
cout << endl;*/
}
ll res = 0;
for (int i = 1; i <= n; i ++)
res += p[i];
for (pair < int, ll > cur : upd[n])
{
if (cur.first <= m)
res += cur.second;
}
res = res + dp[m];
cout << res << endl;
/**for (int i = 0; i <= n; i ++)
{
for (int j = 0; j <= m; j ++)
{
if (i > 0)
{
dp[i][j] = max(dp[i][j], dp[i - 1][j] + (pref[0][i] + pref[1][j] <= s[i]));
}
if (j > 0)
{
dp[i][j] = max(dp[i][j], dp[i][j - 1] + (pref[0][i] + pref[1][j] <= t[j]));
}
///cout << "state " << i << " " << j << " " << dp[i][j] << endl;
}
}
cout << dp[n][m] << endl;*/
}
void solve()
{
input();
prefix_sums();
dynamic();
}
int main()
{
speed();
solve();
return 0;
}
/**
12 12
551691302 324632420 1
800582045 1348372403 1
14063803 14733602 1
52897269 256428825 1
153641504 1321745671 1
567834643 1337247037 1
453508034 1270193155 1
853479486 1945292068 1
949940012 170066870 1
931639209 404493902 1
527379143 3215826828 1
577323364 5341297473 1
454806733 35892194 1
548126558 853228360 1
164112328 683827774 1
646222819 1024075881 1
175848606 1215633462 1
757955322 1494042377 1
998100803 1730743663 1
719046844 3366751190 1
365712755 2424659388 1
776737361 5326686164 1
360112857 2712285166 1
351715858 1314544058 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10090 ms |
23384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14784 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
3 ms |
14816 KB |
Output is correct |
| 6 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 7 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
14840 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14784 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
3 ms |
14816 KB |
Output is correct |
| 6 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 7 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
14840 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14784 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
3 ms |
14816 KB |
Output is correct |
| 6 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 7 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
14840 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14784 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
3 ms |
14816 KB |
Output is correct |
| 6 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 7 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
14840 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14784 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 5 |
Correct |
3 ms |
14816 KB |
Output is correct |
| 6 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 7 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
14840 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10090 ms |
23384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10090 ms |
23384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
