Submission #1080757

#TimeUsernameProblemLanguageResultExecution timeMemory
1080757BoomydayOvertaking (IOI23_overtaking)C++17
65 / 100
3556 ms14672 KiB
//#include "overtaking.h" #include <bits/stdc++.h> using namespace std; using ll = long long; ll SZ = 1001; vector<vector<ll>> arrival(SZ+1, vector<ll>(SZ+1,-1)); //arrival[time][bus] vector<vector<int>> sortOrders; ll n, X_, M_; vector<ll> t, w; vector<ll> S_; vector<ll> w_; void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) { S_ = vector<ll>(S.begin(),S.end()); X_ = X; M_ = M; // sort the buses by leaving time (smallest to largest) then speed (largest to smallest) // the arrival time for each bus is the prefix maximum of this array for(int i=0;i<N;++i){ if (W[i] > X){ t.push_back(T[i]); w.push_back(W[i]); } } w_ = vector<ll>(w.begin(),w.end()); n = t.size(); // output w and t for(int i=0;i<n;++i){ arrival[0][i] = t[i]; } for(int j=1;j<M;++j){ //cout << "Foo" << endl; vector<int> buses(n); for(int i=0;i<n;++i) buses[i] = i; // output buses std::sort(buses.begin(), buses.end(), [&](int a, int b)->bool{ //cout << a << " " << b << endl; if (arrival[j-1][a] < arrival[j-1][b]) return 1; if (arrival[j-1][a] > arrival[j-1][b]) return 0; if (w[a] < w[b]) return 1; return 0; }); //cout << "Foo" << endl; sortOrders.push_back(buses); ll pmax = 0; for (auto& bus:buses){ arrival[j][bus] = max(pmax, arrival[j-1][bus]+w[bus]*(S[j]-S[j-1])); pmax = max(pmax, arrival[j][bus]); } } // output the arrival array return; } long long arrival_time(long long Y) { ll tm = Y; for(int j=1;j<M_;++j){ int bnd = upper_bound(sortOrders[j-1].begin(), sortOrders[j-1].end(),-1,[&](int a, int b)->bool{ if (tm <= arrival[j-1][b]) return 1; return 0; }) - sortOrders[j-1].begin(); if (bnd == 0) { tm += X_*(S_[j]-S_[j-1]); } else { tm = max(tm+ X_*(S_[j]-S_[j-1]), arrival[j][sortOrders[j-1][bnd-1]]); } } return tm; } /* int main() { int L, N, X, M, Q; assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q)); std::vector<long long> T(N); for (int i = 0; i < N; i++) assert(1 == scanf("%lld", &T[i])); std::vector<int> W(N); for (int i = 0; i < N; i++) assert(1 == scanf("%d", &W[i])); std::vector<int> S(M); for (int i = 0; i < M; i++) assert(1 == scanf("%d", &S[i])); std::vector<long long> Y(Q); for (int i = 0; i < Q; i++) assert(1 == scanf("%lld", &Y[i])); fclose(stdin); init(L, N, T, W, X, M, S); std::vector<long long> res(Q); for (int i = 0; i < Q; i++) res[i] = arrival_time(Y[i]); for (int i = 0; i < Q; i++) printf("%lld\n", res[i]); fclose(stdout); return 0; } */
#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...