You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
43 lines
977 B
C++
43 lines
977 B
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 2e5 + 50;
|
|
tuple<int, int, int, int> a[N << 1];
|
|
unsigned long long best[N];
|
|
int main()
|
|
{
|
|
memset(best, 0x3f, sizeof(best));
|
|
int n, x;
|
|
scanf("%d%d", &n, &x);
|
|
for (int i = 0, x, y, z; i < n; i++)
|
|
{
|
|
scanf("%d%d%d", &x, &y, &z);
|
|
a[i << 1] = { x, -1, y, z };
|
|
a[i << 1 | 1] = { y, 1, x, z };
|
|
}
|
|
n <<= 1;
|
|
sort(a, a + n);
|
|
auto ans = numeric_limits<unsigned long long>::max();
|
|
for (int i = 0; i < n; i++)
|
|
{
|
|
int l, r, t, c;
|
|
tie(l, t, r, c) = a[i];
|
|
if (t == -1)
|
|
{
|
|
int time = r - l + 1;
|
|
if (time <= x)
|
|
ans = min(ans, c + best[x - time]);
|
|
}
|
|
if (t == 1)
|
|
{
|
|
int time = l - r + 1;
|
|
best[time] = min(best[time], (unsigned long long)c);
|
|
}
|
|
//printf("** %d %d %d %d %lld\n", l, r, t, c, ans);
|
|
}
|
|
if (ans >= 2e9 + 2)
|
|
ans = -1ll;
|
|
printf("%lld", ans);
|
|
return 0;
|
|
} |