# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
955744 | vjudge1 | Pinball (JOI14_pinball) | C++17 | 1014 ms | 8448 KiB |
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, ma, r = (1LL << 50);
cin >> m >> n;
vector<vector<ll> > v, vv(m);
vector<ll> lp, rp;
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]};
lp.resize(w + 1);
rp.resize(w + 1);
for (i = 0; i <= w; i++)
lp[i] = rp[i] = r;
lp[0] = rp[w] = 0;
ma = r;
ll ml, mr;
for (i = 0; i < m; i++)
{
for (j = vv[i][0]; j < vv[i][1]; j++)
lp[vv[i][1]] = min(lp[vv[i][1]], lp[j] + d[i]);
for (j = vv[i][2]; j > vv[i][1]; j--)
rp[vv[i][1]] = min(rp[vv[i][1]], rp[j] + d[i]);
ll ml, mr;
ml = lp[vv[i][0]];
for (j = w; j > vv[i][0]; j--)
ml = min(ml, lp[j]);
mr = rp[vv[i][2]];
for (j = 0; j < vv[i][2]; j++)
mr = min(mr, rp[j]);
ma = min(ma, ml + mr + d[i]);
}
for (j = 1; j <= w; j++)
rp[j] = min(rp[j], rp[j - 1]);
for (j = w - 1; j >= 0; j--)
lp[j] = min(lp[j], lp[j + 1]);
for (j = 0; j <= w; j++)
ma = min(ma, lp[j] + rp[j]);
if (ma < r)
cout << ma;
else
cout << -1;
return 0;
}
Compilation message (stderr)
# | 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... |