제출 #1026060

#제출 시각아이디문제언어결과실행 시간메모리
1026060Mardonbekhazratov추월 (IOI23_overtaking)C++17
65 / 100
3523 ms34228 KiB
#include "overtaking.h" #include <iostream> #include <array> #include <tuple> #include <algorithm> using namespace std; #define ll long long #define ff first #define ss second int l,n,x,m; vector<pair<long long,int>>t; vector<int>s; vector<vector<ll>>pref; vector<vector<array<long long,3>>>e; void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){ tie(l,n,x,m,s)=tie(L,N,X,M,S); t.resize(n); for(int i=0;i<n;i++){ t[i].first=T[i]; t[i].second=W[i]; } sort(t.begin(),t.end()); e.assign(m,vector<array<ll,3>>(n)); pref.assign(m,vector<ll>(n+1)); for(int i=0;i<n;i++) e[0][i]={t[i].ff,t[i].ss,i}; for(int i=1;i<m;i++){ pref[i][0]=0; int l=0; for(int j=0;j<n;j++){ e[i][j]=e[i-1][j]; if(j>0 && e[i-1][j-1][0]<e[i][j][0]) l=j; e[i][j][0]=max(pref[i][l],e[i][j][0]+1LL*(s[i]-s[i-1])*e[i][j][1]); pref[i][j+1]=max(pref[i][j],e[i][j][0]); } sort(e[i].begin(),e[i].end()); } } long long arrival_time(long long Y){ long long ans=Y; for(int i=1;i<m;i++){ array<ll,3>gg={ans,0,0}; int pos=lower_bound(e[i-1].begin(),e[i-1].end(),gg)-e[i-1].begin(); ans=max(ans+1LL*(s[i]-s[i-1])*x,pref[i][pos]); } return ans; }
#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...