This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll m, n, i, j, k, a, b, w = 0, r = (1LL << 50);
cin >> m >> n;
vector<vector<ll> > v, vv(m), dp, ndp;
vector<ll> d(m), s(3 * m);
for (i = 0; i < m; i++)
{
cin >> j;
v.push_back({j - 1, i, -1});
cin >> j;
v.push_back({j - 1, i, 1});
cin >> j;
v.push_back({j - 1, i, 0});
cin >> d[i];
}
sort(v.begin(), v.end());
if (v[0][0] || v[3 * m - 1][0] != n - 1)
{
cout << -1;
return 0;
}
for (i = 0; i < 3 * m; i++)
{
if (!i)
s[i] = 0;
else if (v[i][0] > v[i - 1][0])
s[i] = s[i - 1] + 1;
else
s[i] = s[i - 1];
w = max(w, s[i]);
}
for (i = 0; i < 3 * m; i++)
v[i] = {v[i][1], s[i], v[i][2]};
sort(v.begin(), v.end());
for (i = 0; i < m; i++)
vv[i] = {v[3 * i][1], v[3 * i + 1][1], v[3 * i + 2][1]};
ndp.resize(w + 1);
for (i = 0; i <= w; i++)
{
ndp[i].resize(i + 1);
for (j = 0; j <= i; j++)
{
if (j == i)
ndp[i][j] = 0;
else
ndp[i][j] = r;
}
}
dp = ndp;
for (i = m - 1; i >= 0; i--)
{
for (j = 0; j <= w; j++)
{
for (k = 0; k <= j; k++)
{
if (dp[j][k] < r && k <= vv[i][1] && vv[i][1] <= j)
{
a = min(k, vv[i][0]);
b = max(j, vv[i][2]);
ndp[b][a] = min(ndp[b][a], dp[j][k] + d[i]);
}
}
}
dp = ndp;
}
if (dp[w][0] < r)
cout << dp[w][0];
else
cout << -1;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |