Submission #1242348

#TimeUsernameProblemLanguageResultExecution timeMemory
1242348banganOvertaking (IOI23_overtaking)C++20
0 / 100
0 ms324 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; 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); } ll arrival_time(ll Y) { t[n] = Y; vector<ll> f = t; for (int i=1; i<m; i++) { vector<ll> new_f = f; for (int j=0; j<=n; j++) new_f[j] = f[j] + (s[i] - s[i-1]) * w[i]; vector<int> ord(n+1); iota(ALL(ord), 0); sort(ALL(ord), [&](int p, int q) { return f[p] < f[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(new_f[*it], mx); for (auto it=l; it!=r; it++) chmax(mx, new_f[*it]); l = r; } f = new_f; } return f[n]; }
#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...