# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
321474 | MetB | Sailing Race (CEOI12_race) | C++14 | 1407 ms | 7404 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 2000000;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
int path[500][500][2], dp[500][500][2], dp_max[500][500][2];
int g[500][500], k;
int ans[500], n, m, nx[500][2];
void f_edge (int l, int r, int dir) {
path[l][r][dir] = 1;
dp[l][r][dir] = 1 + dp_max[r][nx[l][dir]][!dir];
}
void f (int l, int r, int dir) {
for (int k = nx[l][dir]; k != r; k = nx[k][dir]) {
path[l][r][dir] = max (dp[l][r][dir], path[l][k][dir] + path[k][r][dir]);
dp[l][r][dir] = max (dp[l][r][dir], path[l][k][dir] + dp[k][r][dir]);
}
dp_max[l][r][dir] = max (dp[l][r][dir], dp_max[l][nx[r][!dir]][dir]);
}
int main () {
cin >> n >> k;
for (int i = 0; i < n; i++) {
int x;
while (cin >> x && x) {
g[i][x-1] = 1;
}
nx[i][0] = (i + 1) % n;
nx[i][1] = i ? i - 1 : n - 1;
}
for (int k = 1; k < n; k++)
for (int i = 0; i < n; i++) {
int l = i, r = (i + k) % n;
if (g[l][r]) f_edge (l, r, 0);
if (g[r][l]) f_edge (r, l, 1);
f (l, r, 0);
f (r, l, 1);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int dir = 0; dir < 2; dir++)
ans[i] = max (ans[i], dp[i][j][dir]);
if (!k) {
int ind = max_element(ans, ans + n) - ans;
cout << ans[ind] << ' ' << ind + 1 << endl;
return 0;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int dir = 0; dir < 2; dir++) {
int k = nx[j][dir];
if (!path[i][j][dir]) continue;
while (k != i && !g[k][i]) k = nx[k][dir];
if (k == i) continue;
for (int l = nx[k][dir]; l != i; l = nx[l][dir]) {
int ans_l = max(dp_max[l][nx[k][dir]][!dir], dp_max[l][nx[i][!dir]][dir]);
if (g[j][l]) ans[k] = max (ans[k], 2 + path[i][j][dir] + ans_l);
//cout << k << ' ' << i << ' ' << j << ' ' << l << ' ' << 2 + path[i][j][dir] + ans_l << endl;
}
}
int ind = max_element(ans, ans + n) - ans;
cout << ans[ind] << ' ' << ind + 1 << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |