| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1016718 | tmarcinkevicius | Overtaking (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
//void init(int32_t _L, int32_t _N, vector<int64_t> _T, vector<int32_t> _W, int32_t _X, int32_t _M, vector<int32_t> _S);
//long long arrival_time(long long Y);
vector<vector<int64_t>> Expected, Real;
int32_t L;
int32_t N;
vector<int64_t> T;
vector<int32_t> W;
int32_t X;
int32_t M;
vector<int32_t> S;
void init(int32_t _L, int32_t _N, vector<int64_t> _T, vector<int32_t> _W, int32_t _X, int32_t _M, vector<int32_t> _S)
{
_W.push_back(_X);
L = _L;
N = _N;
T = _T;
W = _W;
X = _X;
M = _M;
S = _S;
return;
}
int64_t arrival_time(int64_t Y)
{
Expected = vector<vector<int64_t>>(N + 1);
Real = vector<vector<int64_t>>(N + 1);
T.push_back(Y);
for (int i = 0; i <= N; i++)
{
Expected[i] = vector<int64_t>(M);
Real[i] = vector<int64_t>(M);
Expected[i][0] = T[i];
Real[i][0] = T[i];
}
for (int i = 1; i < M; i++)
{
int dis = S[i] - S[i - 1];
for (int j = 0; j <= N; j++)
{
Expected[j][i] = Real[j][i - 1] + dis * W[j];
}
for (int j = 0; j <= N; j++)
{
Real[j][i] = Expected[j][i];
for (int z = 0; z <= N; z++)
{
if (z == j)
continue;
if (Real[z][i - 1] < Real[j][i - 1])
{
Real[j][i] = max(Real[j][i], Expected[z][i]);
}
}
}
}
/*for (int i = 0; i <= N; i++)
{
cout << "i = " << i << " ";
for (int j = 0; j < M; j++)
{
cout << "|e: " << setw(4) << Expected[i][j] << ", r: " << setw(4) << Real[i][j] << "| ";
}
cout << '\n';
}*/
T.pop_back();
return Real[N][M - 1];
}
/*int32_t main()
{
int _L, _N, _X, _M, _Q;
cin >> _L >> _N >> _X >> _M >> _Q;
vector<int64_t> _T(_N);
for (int i = 0; i < _N; i++)
cin >> _T[i];
vector<int32_t> _W(_N);
for (int i = 0; i < _N; i++)
cin >> _W[i];
vector<int32_t> _S(_M);
for (int i = 0; i < _M; i++)
cin >> _S[i];
vector<int> _Y(_Q);
for (int i = 0; i < _Q; i++)
cin >> _Y[i];
init(_L, _N, _T, _W, _X, _M, _S);
vector<int> res(_Q);
for (int i = 0; i < _Q; i++)
res[i] = arrival_time(_Y[i]);
for (int i = 0; i < _Q; i++)
cout << res[i] << '\n';
}*/