#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdint>
#include <queue>
using namespace std;
int main () {
int n = 0, l = 0;
cin >> n >> l;
vector <int> X (n + 1);
for (int i = 1; i <= n; i++)
cin >> X[i];
vector <int> T (n + 1);
for (int i = 1; i <= n; i++)
cin >> T[i];
vector <int> prefX (n + 2);
prefX[1] = 0;
for (int i = 2; i <= n + 1; i++) {
if (i <= n)
prefX[i] = prefX[i - 1] + (X[i] - X[i - 1]);
else
prefX[i] = prefX[i - 1] + ((l - X[n]) + X[1]);
}
// Testing some stuff
// cout << prefX[4] - prefX[3] << '\n';
// for (int i = 1; i <= n + 1; i++) {
// cout << 2 << ' ' << (i - 1 % n) + 1 << " | " << prefX[i] - prefX[2] << '\n';
// }
// u could just do this...
// time point vector index
priority_queue <pair <int, pair <int, int> >, vector <pair <int, pair <int, int> > >, greater <pair <int, pair <int, int> > > > s;
vector <vector <bool> > v;
vector <int> rem;
rem.reserve (n * n);
v.reserve (n * n);
int free = 0;
// template
vector <bool> template1 (n + 1);
for (int i = 1; i <= n; i++) {
int mindist = min (
prefX[i] + X[1],
l - (prefX[i] + X[1])
);
if (mindist > T[i])
continue;
s.push ({
mindist,
{
i,
free++
}
});
// cout << i << ' ' << mindist << '\n';
template1[i] = 1;
v.push_back (template1);
rem.push_back (1);
template1[i] = 0;
}
// deallocate template1
// vector <bool> ().swap (template1);
int ans = 0;
// dijksta
while (!s.empty()) {
int p = s.top().second.first;
int cont = s.top().second.second;
int time = s.top().first;
s.pop ();
// cout << p << ' ' << time << ' ' << rem[cont] << " | ";
// for (bool e : v[cont])
// cout << e << ' ';
// cout << '\n';
ans = max (ans, rem[cont]);
for (int e = 1; e <= n; e++)
if (e != p) {
int mindist = min (
abs (prefX[e] - prefX[p]),
l - abs (prefX[e] - prefX[p])
);
if (mindist + time <= T[e] && v[cont][e] == 0) {
s.push ({
mindist + time,
{
e,
free++
}
});
v[cont][e] = 1;
v.push_back (v[cont]);
rem.push_back (rem[cont] + 1);
v[cont][e] = 0;
}
}
// deallocate
// vector <bool> ().swap (v[cont]);
}
cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
432 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
436 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
14 ms |
5192 KB |
Output is correct |
13 |
Correct |
5 ms |
1444 KB |
Output is correct |
14 |
Correct |
0 ms |
436 KB |
Output is correct |
15 |
Correct |
1 ms |
432 KB |
Output is correct |
16 |
Execution timed out |
2107 ms |
739072 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
432 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
436 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
14 ms |
5192 KB |
Output is correct |
13 |
Correct |
5 ms |
1444 KB |
Output is correct |
14 |
Correct |
0 ms |
436 KB |
Output is correct |
15 |
Correct |
1 ms |
432 KB |
Output is correct |
16 |
Execution timed out |
2107 ms |
739072 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
432 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
436 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
14 ms |
5192 KB |
Output is correct |
13 |
Correct |
5 ms |
1444 KB |
Output is correct |
14 |
Correct |
0 ms |
436 KB |
Output is correct |
15 |
Correct |
1 ms |
432 KB |
Output is correct |
16 |
Execution timed out |
2107 ms |
739072 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
432 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
436 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
14 ms |
5192 KB |
Output is correct |
13 |
Correct |
5 ms |
1444 KB |
Output is correct |
14 |
Correct |
0 ms |
436 KB |
Output is correct |
15 |
Correct |
1 ms |
432 KB |
Output is correct |
16 |
Execution timed out |
2107 ms |
739072 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |