제출 #1284997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284997		tudor_costin	치료 계획 (JOI20_treatment)	C++20	0 / 100	103 ms	1844 KiB

treatment

#include <bits/stdc++.h>

using namespace std;
const int Mmax=1e5+5;
struct tratament
{
    int t,l,r,c;
};
tratament trat[Mmax];
bool viz[Mmax];
vector<pair<int,int>> g[Mmax];
int main()
{
    int n,m;
    cin>>n>>m;
    priority_queue<pair<int,int>> pq;
    bool ok=1;
    for(int i=1;i<=m;i++)
    {
        cin>>trat[i].t>>trat[i].l>>trat[i].r>>trat[i].c;
        if(trat[i].t!=1) ok=0;
        if(trat[i].l==1)
        {
            pq.push({-trat[i].c,i});
        }
    }
    assert(!ok);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j==i) continue;
            if(trat[i].t<trat[j].t)
            {
                if(trat[i].r+trat[i].t>=trat[j].l+trat[j].t-1) g[i].push_back({j,trat[j].c});
            }
            else
            {
                 if(trat[i].r-trat[i].t>=trat[j].l-trat[j].t-1) g[i].push_back({j,trat[j].c});
            }
        }
    }
    while(!pq.empty())
    {
        auto [val,nod]=pq.top();
        pq.pop();
        if(viz[nod]) continue;
        ///cout<<nod<<' '<<-val<<'\n';
        viz[nod]=1;
        if(trat[nod].r==n)
        {
            cout<<-val<<'\n';
            return 0;
        }
        for(auto [u,cost]:g[nod])
        {
            if(!viz[u]) pq.push({val-cost,u});
        }
    }
    cout<<-1<<'\n';
    return 0;
}

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