제출 #583008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583008		elkernos	치료 계획 (JOI20_treatment)	C++17	35 / 100	3048 ms	7372 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

struct treatment {
    int t, l, r, c;
    pair<int, int> pocz, kon;
    void read()
    {
        cin >> t >> l >> r >> c;
        r++;
        pocz.first = l + t;
        pocz.second = t - l;
        kon.first = r + t;
        kon.second = t - r;
    }
};

int main()
{
    cin.tie(nullptr)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<treatment> they(m + 1);
    for(int i = 1; i <= m; i++) {
        they[i].read();
    }
#define T pair<long long, int>
    priority_queue<T, vector<T>, greater<T>> q;
    const long long ool = 1e18 + 5;
    vector<long long> d(m + 1);
    for(int i = 1; i <= m; i++) {
        if(they[i].l == 1) {
            d[i] = they[i].c;
            q.push({d[i], i});
        }
        else {
            d[i] = ool;
        }
    }
    while(!q.empty()) {
        pair<long long, int> t = q.top();
        q.pop();
        assert(t.first == d[t.second]);
        for(int i = 1; i <= m; i++) {
            if(d[i] > t.first + they[i].c && they[i].pocz.first <= they[t.second].kon.first && they[i].pocz.second >= they[t.second].kon.second) {
                q.emplace(d[i] = t.first + they[i].c, i);
            }
        }
    }
    long long ans = ool;
    for(int i = 1; i <= m; i++) {
        if(they[i].r == n + 1) {
            ans = min(ans, d[i]);
        }
    }
    cout << (ans == ool ? -1 : ans) << '\n';
}

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