Submission #202248

#TimeUsernameProblemLanguageResultExecution timeMemory
202248grtSegway (COI19_segway)C++17
15 / 100
17 ms1268 KiB
#include <bits/stdc++.h> #define PB push_back #define ST first #define ND second #define _ ios_base::sync_with_stdio(0); cin.tie(0); //mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); using namespace std; using ll = long long; using pi = pair<int,int>; using vi = vector<int>; struct Trip { int a,b,c; bool operator < (const Trip&Tr) const { return a<Tr.a; } }; const int nax = 20*1000+10,kax = 300+5; int n,m; Trip v[nax]; int station[kax]; int nxt[kax][21]; int cnt[kax]; bool visited[nax][kax]; int ans[nax]; priority_queue<Trip>PQ; int driving_time(int id,int x,int y) { int t = 0; t += (min(y,100)-min(x,100))*v[id].a; x = max(100,x); y = max(100,y); t += (min(y,200)-min(x,200))*v[id].b; x = max(200,x); y = max(200,y); t += (y-x)*v[id].c; return t; } int main() {_ cin>>n; for(int i=1; i<=n; i++) { cin>>v[i].a>>v[i].b>>v[i].c; } cin>>m; for(int i=1; i<=m; i++) { cin>>station[i]; } for(int i=1; i<=m; i++) { nxt[i][20] = m+1; for(int j=i+1; j<=m; j++) { if(nxt[i][min(19,station[j]-station[i])]==0) { nxt[i][min(19,station[j]-station[i])]=j; } else { break; } } for(int j=19; j>=0; j--) { if(nxt[i][j]==0) nxt[i][j] = nxt[i][j+1]; } } if(m==0) { for(int i=1; i<=n; i++) { cout<<driving_time(i,0,300)<<"\n"; } return 0; } for(int i=1; i<=n; i++) { PQ.push({-driving_time(i,0,station[1]),i,1}); } station[m+1] = 300; int last = -1; vi delta = {}; while(!PQ.empty()) { Trip tp = PQ.top(); tp.a = -tp.a; if(tp.a!=last) { for(auto x:delta) { cnt[x]++; } last = tp.a; delta.clear(); } delta.PB(tp.c); PQ.pop(); // cover case when more than one driver have same time if(tp.c==m+1) { ans[tp.b] = tp.a; continue; } int d = min(300-station[tp.c],cnt[tp.c]%20); int nx = nxt[tp.c][d]; int t1 = tp.a+driving_time(tp.b,station[tp.c]+d,station[nx])+d; PQ.push({-t1,tp.b,nx}); } for(int i=1; i<=n; i++) { cout<<ans[i]<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...