Submission #1126567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126567		12345678	Treatment Project (JOI20_treatment)	C++20	5 / 100	153 ms	884 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);
    }
    //cout<<"debug "<<dpl[1]<<' '<<dpr[1]<<'\n';
    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]);
    for (int i=1; i<=m; i++) if (p[i].l==1&&p[i].r==n) res=min(res, p[i].c);
    if (res!=1e18) cout<<res;
    else cout<<-1;
}

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

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