이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
typedef long long ll;
typedef pair <ll,int> bus;
bool operator<(bus a, bus b)
{
if(a.first<b.first)
{
return true;
}
if(a.first==b.first && a.second<b.second)
{
return true;
}
return false;
}
bus busses[1001][1001];
ll stuck[1001][1001];
int n;
int m;
vector <int> s;
int x;
bool yolo;
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;
if(N==0)
{
yolo=true;
return;
}
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.first+=((ll)(S[i]-S[i-1]))*curr.second;
if(curr.first>maxi)
{
maxi=curr.first;
}
else
{
curr.first=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].first;
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].first==busses[i][j-1].first)
{
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].first)
{
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)
{
if(yolo)
{
return Y+((ll)(s[m-1]-s[0]))*x;
}
int j=n;
for(int k=9;k>=0;k--)
{
int next_j=max(0,j-(1<<k));
if(Y<=busses[0][next_j].first)
{
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].first)
{
curr=nxt;
}
}
curr++;
if(curr==m)
{
return Y+((ll)(s[m-1]-s[0]))*x;
}
return stuck[curr][j];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |