| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 841984 | Huseyn123 | Overtaking (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define MAX 1000001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
for(int i=0;i<b;i++){\
cin >> a[i];\
}\
}
#define inputvec(a,b){\
for(int i=0;i<b;i++){\
ll num;\
cin >> num;\
a.pb(num);\
}\
}
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << x << " ";\
}\
cout << "\n";\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
int n,m,q,spd,road_len,b[1001],d[1001];
ll a[1001];
void solve(){
cin >> road_len >> n >> spd >> m >> q;
for(int i=0;i<n;i++){
cin >> a[i];
}
// a avtobusların çıxma vaxtı üçün
for(int i=0;i<n;i++){
cin >> b[i];
}
// b avtobusların sürətləri üçün
for(int i=0;i<m;i++){
cin >> d[i];
}
// d stansiyalar üçün
ll e[n][m];
// e stansiyalara çatma vaxtı üçün
vector<pll> g[m];
ll p[n][m];
// p g prefix max üçün
for(int i=0;i<n;i++){
e[i][0]=a[i];
}
for(int j=1;j<m;j++){
vector<pll> f; // avtobusların stansiyaya çatma vaxtına əsasən sıralayıb digər stansiyaya çatma vaxtını o(n)-ə hesablamaq üçün
for(int i=0;i<n;i++){
f.pb(mp(e[i][j-1],i));
}
sortv(f);
g[j-1]=f;
ll h=-1; // digər stansiyaya max çatma vaxtı
int z=0;
while(z<n){
int z1=z;
while(z1<n && f[z1].ff==f[z].ff){
e[f[z1].ss][j]=max(h,f[z1].ff+b[f[z1].ss]*(d[j]-d[j-1]));
z1++;
}
while(z<z1){
h=max(h,e[f[z].ss][j]);
z++;
}
}
}
vector<pll> f;
for(int i=0;i<n;i++){
f.pb(mp(e[i][m-1],i));
}
sortv(f);
g[m-1]=f;
for(int j=0;j<m;j++){
p[0][j]=g[j][0].ff;
for(int i=1;i<n;i++){
p[i][j]=max(p[i-1][j],g[j][i].ff);
}
}
for(int i=0;i<q;i++){
ll x;
cin >> x;
for(int j=0;j<m-1;j++){
pll p1=mp(x,-1);
auto it=ub(g[j],p1);
x+=(d[j+1]-d[j])*spd;
if(it!=g[j].begin()){
--it;
int ind=it-g[j].begin();
x=max(x,p[ind][j+1]);
}
}
cout << x << "\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin >> t;
ll cnt1=1;
while(t--){
solve();
cnt1++;
}
}