Submission #1194381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194381		hengliao	Train (APIO24_train)	C++20	5 / 100	40 ms	10680 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll mxN=1005;
    const ll inf=1e18;
    ll n, m, w;
    vll t, x, y, a, b, c, l, r;
    vll con;

    vll in[mxN], out[mxN];
    deque<ll> dq[mxN];
    ll dp[mxN];

    ll id(ll tar){
        return lower_bound(con.begin(), con.end(), tar)-con.begin();
    }

    ll f(ll idx, ll time){
        if(dp[idx]==inf) return inf;
        ll re=dp[idx];
        for(ll i=0;i<w;i++){
            if(l[i]>b[idx] && r[i]<time){
                re+=t[y[idx]];
            }
        }
        return re;
    }   

    ll inter(ll idx1, ll idx2){
        ll lef=id(b[idx2]), rig=(ll) con.size()-1;
        ll re=inf;
        while(lef<=rig){
            ll mid=(lef+rig)/2;
            if(f(idx1, con[mid])>=f(idx2, con[mid])){
                re=con[mid];
                rig=mid-1;
            }
            else{
                lef=mid+1;
            }
        }
        return re;
    }
}

long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y,
                vector<int> A, vector<int> B, vector<int> C, vector<int> L,
                vector<int> R) {
    con.clear();
	n=N;
    m=M;
    w=W;
    t=vll(n, 0);
    for(ll i=0;i<n;i++){
        t[i]=T[i];
    }
    x=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        x[i]=X[i];
    }
    y=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        y[i]=Y[i];
    }
    a=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        a[i]=A[i];
        con.pb(a[i]);
    }
    b=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        b[i]=B[i];
        con.pb(b[i]);
    }
    c=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        c[i]=C[i];
    }
    l=vll(w, 0);
    for(ll i=0;i<w;i++){
        l[i]=L[i];
        con.pb(l[i]);
    }
    r=vll(w, 0);
    for(ll i=0;i<w;i++){
        r[i]=R[i];
        con.pb(r[i]);
    }
    con.pb(0);
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
    x[m]=0;
    y[m]=0;
    a[m]=0;
    b[m]=0;
    c[m]=0;
    dp[m]=0;
    for(ll i=0;i<m;i++){
        in[id(a[i])].pb(i);
        out[id(b[i])].pb(i);
    }
    dq[id(0)].pb(m);
    for(ll i=0;i<(ll) con.size();i++){
        for(auto &it:out[i]){
            if(dp[it]==inf) continue;
            ll tar=y[it];
            while((ll) dq[tar].size()>=2 && inter(dq[tar][(ll) dq[tar].size()-2], it)<=
            inter(dq[tar][(ll) dq[tar].size()-2], dq[tar][(ll) dq[tar].size()-1])){
                dq[tar].pop_back();
            }
            if(dq[tar].empty() || inter(dq[tar][(ll) dq[tar].size()-1], it)!=inf){
                dq[tar].pb(it);
            }
        }
        for(auto &it:in[i]){
            ll tar=x[it];
            if(dq[tar].empty()){
                dp[it]=inf;
                continue;
            }
            while((ll) dq[tar].size()>=2 && f(dq[tar][1], a[it])<=
            f(dq[tar][0], a[it])){
                dq[tar].pop_front();
            }
            dp[it]=f(dq[tar][0], a[it])+c[it];
            dp[it]=min(dp[it], inf);
        }
    }
    ll ans=inf;
    for(ll i=0;i<m;i++){
        // cout<<i<<' '<<dp[i]<<'\n';
        if(y[i]==n-1){
            ans=min(ans, f(i, inf));
        }
    }
    if(ans==inf) return -1;
    return ans;
}

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