제출 #1126565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126565		12345678	치료 계획 (JOI20_treatment)	C++17	0 / 100	2 ms	576 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

const int nx=5e3+5;

#define ll long long

struct plan
{
    ll l, r, t, c;
} p[nx];

ll n, m, dpl[nx], dpr[nx], res=1e18;
vector<pair<ll, ll>> v;

bool isect(int x, int y)
{
    return ((p[x].r+p[x].t)-(p[y].l-p[y].t)+1)/2>=max(p[x].t, p[y].t);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>p[i].t>>p[i].l>>p[i].r>>p[i].c, dpl[i]=dpr[i]=1e18;
    for (int i=1; i<=m; i++) v.push_back({p[i].r+p[i].t, i});
    sort(v.begin(), v.end());
    for (int i=0; i<m; i++)
    {
        int idx=v[i].second;
        if (p[idx].l==1) dpl[idx]=p[idx].c;
        else for (int j=0; j<i; j++) if (isect(v[j].second, idx)) dpl[idx]=min(dpl[idx], dpl[v[j].second]+p[idx].c);
    }
    v.clear();
    for (int i=1; i<=m; i++) v.push_back({p[i].l-p[i].t, i});
    sort(v.begin(), v.end());
    for (int i=m-1; i>=0; i--)
    {
        int idx=v[i].second;
        if (p[idx].r==n) dpr[idx]=p[idx].c;
        else for (int j=i+1; j<m; j++) if (isect(idx, v[j].second)) dpr[idx]=min(dpr[idx], dpr[v[j].second]+p[idx].c);
    }
    for (int i=1; i<=m; i++) for (int j=1; j<=m; j++) if (isect(i, j)) res=min(res, dpl[i]+dpr[j]);
    cout<<res;
}

/*
10 2
1 1 6 1
2 7 10 1
*/

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