| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 848137 | Muaath_5 | 추월 (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define ld long double
using namespace std;
const ll N = 1001, INF = 7e15;
int n, m, l, x;
int pos[N][N], full[N][N];
vector<int> srt[N];
vector<int> spd;
vector<ll> st;
vector<int> len;
int tmp;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
n = N, m = M, l = L, x = X, spd = W, st = T, len = S;
for (int j = 0; j < n; j++) {
pos[0][j] = T[j];
full[0][j] = T[j];
srt[0].push_back(j);
}
sort(srt[0].begin(), srt[0].end(), [](int x, int y) {
return st[x] == st[y] ? spd[x] < spd[y] : st[x] < st[y];
});
for (int i = 0; i < m-1; i++) {
//cout << "Station " << i + 1 << '\n';
pos[i + 1][srt[i][0]] = spd[srt[i][0]] * (len[i + 1] - len[i]) + pos[i][srt[i][0]];
full[i + 1][srt[i][0]] = spd[srt[i][0]] * (len[i + 1] - len[i]) + full[i][srt[i][0]];
srt[i + 1].push_back(0);
//cout << "Bus " << srt[i][0] << " Arrives " << pos[i+1][srt[i][0]] << '\n';
for (int j = 1; j < n; j++) {
srt[i + 1].push_back(j);
full[i + 1][srt[i][j]] = spd[srt[i][j]] * (len[i + 1] - len[i]) + full[i][srt[i][j]];
const ll exp = spd[srt[i][j]] * (len[i + 1] - len[i]) + pos[i][srt[i][j]];
if (exp <= pos[i + 1][srt[i][j - 1]]) {
pos[i + 1][srt[i][j]] = pos[i + 1][srt[i][j - 1]];
//cout << "Intersects: ";
}
else {
pos[i + 1][srt[i][j]] = exp;
}
//cout << "Bus " << srt[i][j] << " Arrives " << pos[i + 1][srt[i][j]] << '\n';
}
tmp = i+1;
sort(srt[i+1].begin(), srt[i+1].end(), [](int x, int y) {
return pos[tmp][x] == pos[tmp][y] ? spd[x] < spd[y] : pos[tmp][x] < pos[tmp][y];
});
}
return;
}
ll arrival_time(ll Y) {
ll tm = Y;
for (int i = 0; i < m-1; i++) {
int idx = -1;
while (idx+1 < n && pos[i][srt[i][idx + 1]] < tm)
idx++;
const ll exp = x * (len[i + 1] - len[i]) + tm;
if (idx == -1) {
tm = exp;
}
else {
int prv = srt[i][idx];
if (exp <= pos[i + 1][prv]) {
tm = pos[i + 1][prv];
}
else {
tm = exp;
}
}
}
return tm;
}