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>
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 100100;
int l[N], r[N], c[N], d[N];
ll pref[N], suf[N];
const ll INF = 1e16 + 128;
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> l[i] >> r[i] >> c[i] >> d[i];
for (int i = 1; i <= m; i++)
pref[i] = suf[i] = INF;
pref[0] = 0;
suf[m + 1] = 0;
ll ans = INF;
for (int i = 0; i < n; i++) {
ll lx = INF, rx = INF;
if (l[i] == 1) lx = 0;
if (r[i] == m) rx = 0;
for (int x = l[i]; x <= c[i]; x++)
lx = min(lx, pref[x]);
for (int x = c[i]; x <= r[i]; x++)
rx = min(rx, suf[x]);
ans = min(ans, lx + rx + d[i]);
if (l[i] == 1)
pref[c[i]] = min(pref[c[i]], 1ll * d[i]);
else for (int x = l[i]; x <= c[i]; x++)
pref[c[i]] = min(pref[c[i]], pref[x] + d[i]);
if (r[i] == m)
suf[c[i]] = min(suf[c[i]], 1ll * d[i]);
else for (int x = c[i]; x <= r[i]; x++)
suf[c[i]] = min(suf[c[i]], pref[x] + d[i]);
}
cout << ans << '\n';
}
main() {
boost;
solve();
return 0;
}
Compilation message (stderr)
pinball.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
56 | main() {
| ^~~~
# | 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... |