제출 #1076380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1076380		MOUF_MAHMALAT	치료 계획 (JOI20_treatment)	C++14	35 / 100	129 ms	10064 KiB

treatment

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pll;
const ll oo= 1e5+9;
const ll inf=1e18;
struct node
{
    ll t,l,r,c;
} a[oo];
bool cmp(const node&A,const node&B)
{
    return A.r < B.r;
}
ll n,m,d[5009];
bool vis[5009];
void solve()
{
    cin>>n>>m;
    for(ll i=0; i<m; i++)
        d[i]=inf;
    for(ll i=0; i<m; i++)
    {
        cin>>a[i].t>>a[i].l>>a[i].r>>a[i].c;
        if(a[i].l==1)
            d[i]=0;
    }
    while(1)
    {
        ll id=-1;
        for(ll i=0; i<m; i++)
        {
            if(id==-1)
            {
                if((!vis[i])&&d[i]<inf)
                    id=i;
            }
            else if(d[id]>d[i]&&!vis[i])
                id=i;
        }
        if(id==-1)
            break;
//        cout<<id<<endl;
//        cout<<d[id]<<"? "<<endl;
        vis[id]=1;
        for(ll i=0; i<m; i++)
        {
            if(a[i].l<=a[id].r-abs(a[id].t-a[i].t)+1)
                d[i]=min(d[i],d[id]+a[id].c);
        }
    }
    ll ans=inf;
    for(ll i=0; i<m; i++)
        if(a[i].r==n&&vis[i])
            ans=min(ans,d[i]+a[i].c);
    if(ans>=inf)
        ans=-1;
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    ll tt=1;
//    cin>>tt;
    while(tt--)
        solve();
    return 0;
}

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