제출 #1068271

#제출 시각아이디문제언어결과실행 시간메모리
1068271amirhoseinfar1385추월 (IOI23_overtaking)C++17
65 / 100
3568 ms126616 KiB
#include "overtaking.h" #include<bits/stdc++.h> using namespace std; const long long maxn=1000+10; long long n,dis[maxn],shib,m; pair<long long,long long>all[maxn]; map<long long,vector<long long>>mp[maxn]; vector<pair<long long,long long>>mpmx[maxn]; long long solve(long long ind,long long y){ // cout<<"solve: "<<ind<<" "<<y<<endl; if(ind==m-1){ return y; } long long fake=shib*(dis[ind+1]-dis[ind])+y; /* for(auto x:mpmx[ind]){ if(x.first>=y){ break; } fake=max(fake,x.second); }*/ int p=lower_bound(mpmx[ind].begin(),mpmx[ind].end(),make_pair(y,-1ll))-mpmx[ind].begin(); if(p!=0){ p--; fake=max(fake,mpmx[ind][p].second); } return solve(ind+1,fake); } void build(){ for(long long i=0;i<m;i++){ long long mx=0; for(auto x:mp[i]){ long long fake=mx; for(auto y:x.second){ mp[i+1][max(fake,x.first+(dis[i+1]-dis[i])*y)].push_back(y); mx=max(mx,x.first+(dis[i+1]-dis[i])*y); // cout<<"wtf: "<<i<<" "<<x.first<<" "<<y<<endl; } mpmx[i].push_back(make_pair(x.first,mx)); } } } 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(long long i=0;i<n;i++){ mp[0][T[i]].push_back(W[i]); all[i]=make_pair(T[i],W[i]); } shib=X; m=M; for(long long i=0;i<m;i++){ dis[i]=S[i]; } build(); return; } long long arrival_time(long long Y) { return solve(0,Y); }
#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...