# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
321467 | MetB | Sailing Race (CEOI12_race) | C++14 | 1364 ms | 7404 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
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... |