제출 #843153

#제출 시각아이디문제언어결과실행 시간메모리
843153yutabi추월 (IOI23_overtaking)C++17
9 / 100
3553 ms23132 KiB
#include <bits/stdc++.h> #include "overtaking.h" using namespace std; typedef long long ll; struct bus { ll time; int speed; }; bool operator<(bus a, bus b) { if(a.time<b.time) { return true; } if(a.time==b.time && a.speed<b.speed) { return true; } return false; } bus busses[1001][1001]; ll stuck[1001][1001]; int n; int m; vector <int> s; int x; void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) { n=N; m=M; s=S; x=X; for(int i=0;i<M;i++) { set <bus> st; if(i==0) { int skipped=0; for(int j=0;j<N;j++) { if(W[j]<=X) { skipped++; continue; } st.insert({T[j],W[j]}); } N-=skipped; n-=skipped; for(int j=0;j<N;j++) { busses[0][j]=*st.begin(); st.erase(st.begin()); } continue; } ll maxi=-1; for(int j=0;j<N;j++) { bus curr=busses[i-1][j]; curr.time+=((ll)(S[i]-S[i-1]))*curr.speed; if(curr.time>maxi) { maxi=curr.time; } else { curr.time=maxi; } st.insert(curr); } for(int j=0;j<N;j++) { busses[i][j]=*st.begin(); st.erase(st.begin()); } } /*for(int i=0;i<M;i++) { for(int j=0;j<N;j++) { printf("%lld %d ",busses[i][j].time,busses[i][j].speed); } printf("\n"); }*/ for(int i=M-1;i>0;i--) { for(int j=0;j<N;j++) { ll curr=busses[i][j].time; if(i==M-1) { stuck[i][j]=curr; continue; } if(j==0) { stuck[i][j]=curr+((ll)(S[M-1]-S[i]))*X; continue; } if(j>0 && busses[i][j].time==busses[i][j-1].time) { stuck[i][j]=stuck[i][j-1]; continue; } int curr_loc=i; for(int k=9;k>=0;k--) { int next_loc=curr_loc+(1<<k); next_loc=min(next_loc,M-1); ll nxt=curr; nxt+=((ll)(S[next_loc]-S[i]))*X; if(nxt>busses[next_loc][j-1].time) { curr_loc=next_loc; } } curr_loc++; if(curr_loc==M) { stuck[i][j]=curr+((ll)(S[M-1]-S[i]))*X; continue; } stuck[i][j]=stuck[curr_loc][j-1]; } } /*for(int i=1;i<M;i++) { for(int j=0;j<N;j++) { printf("%lld ",stuck[i][j]); } printf("\n"); }*/ return; } long long arrival_time(long long Y) { int j=n; for(int k=9;k>=0;k--) { int next_j=max(0,j-(1<<k)); if(Y<=busses[0][next_j].time) { j=next_j; } } j--; if(j==-1) { return Y+((ll)(s[m-1]-s[0]))*x; } int curr=0; for(int k=9;k>=0;k--) { int nxt=min(curr+(1<<k),m-1); ll t=Y+((ll)(s[nxt]-s[0]))*x; if(t>busses[nxt][j].time) { curr=nxt; } } curr++; if(curr==m) { return Y+((ll)(s[m-1]-s[0]))*x; } return stuck[curr][j]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...