Submission #770397

#	Time	Username	Problem	Language	Result	Execution time	Memory
770397		PurpleCrayon	Treatment Project (JOI20_treatment)	C++17	35 / 100	3011 ms	5848 KiB

treatment

#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 998244353;
const ll INF = 1e18+10;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

void solve() {
    int n, m; cin >> n >> m;
    vector<ar<int, 4>> a(m);
    for (auto& [t, l, r, x] : a) cin >> t >> l >> r >> x, --l, --r;

    min_pq<pair<ll, int>> q;
    vector<ll> dist(m, INF);
    for (int i = 0; i < m; i++) {
        auto [t, l, r, x] = a[i];
        if (l == 0) {
            dist[i] = x;
            q.push({dist[i], i});
        }
    }

    while (!q.empty()) {
        auto [d_c, c] = q.top(); q.pop();
        if (dist[c] != d_c) continue;

        for (int i = 0; i < m; i++) {
            auto [t, l, r, x] = a[i];
            int shrink = abs(t - a[c][0]);
            if (l - a[c][2] + shrink > 1) continue;
            if (dist[c] + x < dist[i]) {
                dist[i] = dist[c] + x;
                q.push({dist[i], i});
            }
        }
    }

    ll ans = INF;
    for (int i = 0; i < m; i++) {
        auto [t, l, r, x] = a[i];
        if (r == n-1) {
            ans = min(ans, dist[i]);
        }
    }

    if (ans >= INF) {
        cout << -1 << '\n';
        return;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61