제출 #1061722

#제출 시각아이디문제언어결과실행 시간메모리
1061722mychecksedad추월 (IOI23_overtaking)C++17
65 / 100
3550 ms71504 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define ll long long #define ff first #define ss second const int N = 3005; const ll INF = 1e18; set<pair<ll, ll>> pref[N]; vector<ll> T, W, S; ll n, m, x, L; void init(int Ll, int nn, std::vector<long long> t, std::vector<int> w, int xx, int mm, std::vector<int> s) { L = Ll, n=nn, m=mm, x=xx; for(int i = 0; i < n; ++i){ if(w[i] > x) W.pb(w[i]), T.pb(t[i]); } for(int f: s) S.pb(f); // W.pb(x); S.pb(Ll); n = W.size(); vector<pair<ll, int>> F; for(int i =0; i < n; ++i) F.pb({W[i], i}); sort(all(F)); reverse(all(F)); vector<vector<ll>> dp(n + 1, vector<ll>(m + 2)); for(int i = 0; i < n; ++i){ dp[i][0] = T[F[i].ss]; for(int j = 1; j <= m; ++j){ ll mx = dp[i][j - 1] + F[i].ff * (S[j] - S[j-1]); auto pos = pref[j].lower_bound(pair<ll,ll>{dp[i][j - 1], -1}); if(pos == pref[j].begin()){ dp[i][j] = mx; }else{ pos = prev(pos); dp[i][j] = max(mx, (*pos).ss); } pref[j].insert({dp[i][j - 1], dp[i][j]}); } } return; } long long arrival_time(long long Y) { ll cur = Y; for(int j = 1; j <= m; ++j){ ll mx = cur + x * (S[j] - S[j-1]); auto pos = pref[j].lower_bound(pair<ll,ll>{cur, -1}); if(pos == pref[j].begin()){ cur = mx; }else{ pos = prev(pos); cur = max(mx, (*pos).ss); } } return cur; }
#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...