| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 980986 | vjudge1 | 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 endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<ll>;using ii = pair<ll,ll>;using mii = map<ll,ll>;
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
int l,n,x,m;vector<ll> t,w;vi s;
void init(int L, int N, vector<ll> T, vector<ll> W, int X,int M,vi S){
l=L,n=N,t=T,w=W,x=X,m=M,s=S;
}
// void en(){cout<<endl;}
// void print(vector<ll> a){
// for( auto v :a) cout << v << " "; cout << endl;
// }
// void print(vector<pair<ll,ll>> a){
// for(auto v: a) cout <<"[" << v.f <<", " << v.s << "]" << endl;
// }
// void print(map<ll, vector<ll>> a){
// for(auto [key, val] : a){
// cout << "[key : " << key << "]" << endl;
// for(auto tt : val)cout<<tt<<" ";en();
// }
// }
ll arrival_time(ll tim){
vector<ll> ex(n+1);vector<pair<ll,ll>>ti(n+1);
for(int i = 0;i < n; i++)ti[i] = {t[i],i};ti[n]={tim,n};
// print(ex);en();print(ti);en();
for(int i = 1; i < m;i++ ){
for(int j = 0; j < n;j++)ex[j] = ti[j].f + (w[j] * (s[i]- s[i-1]));
ex[n] = ti[n].f + (x * (s[i] - s[i-1]));
// print(ex);en();print(ti);en();
map<ll, vector<ll>> nv;for(int j = 0;j <= n;j++)nv[ti[j].f].pb(j);
ll mx = 0;auto newti = ti;
// print(nv);
for(auto [key, val] : nv){
for(auto v: val){
newti[v] = {v, max(mx, ex[v])};
}
for(auto v : val)mx = max(mx, ex[v]);
}
sort(all(newti));
for(int j = 0; j<= n;j++)ti[j] = {newti[j].s, newti[j].f};
// print(ti);en();
}
return ti[n].f;
}