## Submission #202252

# Submission time Handle Problem Language Result Execution time Memory
202252 2020-02-14T14:34:23 Z grt Segway (COI19_segway) C++17
15 / 100
18 ms 1140 KB
```#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];
for(int i=tp.c+1; i<nx; i++) delta.PB(i);
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";
}
}
```

#### Subtask #1 15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 18 ms 1140 KB Output is correct

#### Subtask #2 0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

#### Subtask #3 0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 18 ms 1140 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -