Submission #911160

#TimeUsernameProblemLanguageResultExecution timeMemory
911160NeltOvertaking (IOI23_overtaking)C++17
0 / 100
2 ms2392 KiB
#include "overtaking.h" #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,avx2,fma,popcnt") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> /* DEFINES */ #define S second #define F first #define ll long long #define ull unsigned long long #define ld long double #define npos ULLONG_MAX #define INF LLONG_MAX #define vv(a) vector<a> #define ss(a) set<a> #define pp(a, b) pair<a, b> #define mm(a, b) map<a, b> #define qq(a) queue<a> #define pq(a) priority_queue<a> #define ump(a, b) unordered_map<a, b> #define ANDROID \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define allc(a) begin(a), end(a) #define all(a) a, a + sizeof(a) / sizeof(a[0]) #define elif else if #define endl "\n" #define pb push_back #define ins insert #define logi __lg #define sqrt sqrtl #define mpr make_pair using namespace std; using namespace __cxx11; using namespace __gnu_pbds; typedef char chr; typedef basic_string<chr> str; template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 1005; ll t[N][N]; ll v[N], s[N]; ll n, m; 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, m = M; for (ll i = 0; i < n; i++) t[i][0] = T[i]; for (ll i = 0; i < n; i++) v[i] = W[i]; v[n] = X; for (ll i = 0; i < m; i++) s[i] = S[i]; } long long arrival_time(long long Y) { t[n][0] = Y; vv(pp(ll, ll)) tmp; for (ll i = 0; i <= n; i++) tmp.pb(mpr(v[i], i)); sort(allc(tmp), greater()); for (ll i = 1; i < m; i++) { ll mx[n]; for (ll x = 0; x <= n; x++) { ll j = tmp[x].S; t[j][i] = t[j][i - 1] + v[j] * (s[i] - s[i - 1]); mx[x] = max(x > 0 ? mx[x - 1] : 0, t[j][i]); ll pos = 0ll + lower_bound(allc(tmp), mpr(v[j], (ll)1e9), greater()) - tmp.begin() - 1; if (pos >= 0) t[j][i] = max(t[j][i], mx[pos]); } } return t[n][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...