Submission #1194381

#TimeUsernameProblemLanguageResultExecution timeMemory
1194381hengliao은하철도 (APIO24_train)C++20
5 / 100
40 ms10680 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...