Submission #1242397

#TimeUsernameProblemLanguageResultExecution timeMemory
1242397banganOvertaking (IOI23_overtaking)C++20
9 / 100
3 ms584 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define chmin(a, b) a = min(a, b) #define chmax(a, b) a = max(a, b) #define pb push_back #define ALL(a) a.begin(), a.end() int n; vector<ll> t, w; int m; vector<ll> s; vector<vector<ll>> f; vector<vector<ll>> pre; vector<vector<ll>> og; void prep() { f = vector(m, vector<ll>(n)); pre = og = vector(m, vector<ll>(n+1)); for (int i=0; i<n; i++) f[0][i] = t[i]; // { // vector<int> ord(n); // iota(ALL(ord), 0); // sort(ALL(ord), [&](int p, int q) { // return f[0][p] < f[0][q]; // }); // // for (int i=1; i<=n; i++) pre[0][i] = max(pre[0][i-1], f[0][i-1]); // } for (int i=1; i<m; i++) { for (int j=0; j<n; j++) f[i][j] = f[i-1][j] + (s[i] - s[i-1]) * w[j]; vector<int> ord(n); iota(ALL(ord), 0); sort(ALL(ord), [&](int p, int q) { return f[i-1][p] < f[i-1][q]; }); ll mx=0; for (auto l=ord.begin(); l != ord.end();) { auto r = l; while (r != ord.end() && f[*l]==f[*r]) r++; for (auto it=l; it!=r; it++) chmax(f[i][*it], mx); for (auto it=l; it!=r; it++) chmax(mx, f[i][*it]); l = r; } for (int j=1; j<=n; j++) og[i][j] = f[i-1][ord[j-1]]; for (int j=1; j<=n; j++) pre[i][j] = max(pre[i][j-1], f[i][ord[j-1]]); } } 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; for (auto it : T) t.pb(it); t.pb(0); for (auto it : W) w.pb(it); w.pb(X); m = M; for (auto it : S) s.pb(it); assert(s[0]==0); assert(s[m-1]==L); prep(); } ll arrival_time(ll Y) { vector<ll> res(m); res[0] = Y; for (int i=1; i<m; i++) { int lo=0, hi=n; while (lo<hi) { int mid = (lo+hi+1) / 2; res[i-1] <= og[i][mid] ? hi = mid-1 : lo = mid; } res[i] = max(res[i-1] + w[n] * (s[i] - s[i-1]), pre[i][lo]); } return res[m-1]; }
#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...