제출 #1259411

#제출 시각아이디문제언어결과실행 시간메모리
1259411mtshastaSailing Race (CEOI12_race)C++20
100 / 100
812 ms5332 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m, k, q, type, edge[501][501], dp[501][501][2], dp1[501][501][2], nx[501][2]; string s; void solve(int l, int r, int x) { if (edge[l][r]) { dp[l][r][x] = 1; dp1[l][r][x] = 1 + dp1[r][nx[l][x]][x ^ 1]; } else dp[l][r][x] = dp1[l][r][x] = -1e9; for (int m = nx[l][x]; m != r; m = nx[m][x]) { dp[l][r][x] = max(dp[l][r][x], dp[l][m][x] + dp[m][r][x]); dp1[l][r][x] = max(dp1[l][r][x], dp[l][m][x] + dp1[m][r][x]); } dp1[l][r][x] = max(dp1[l][r][x], dp1[l][nx[r][x ^ 1]][x]); } int main() { cin >> n >> type; for (int i = 0, x; i < n; i++) { while (cin >> x && x-- != 0) edge[i][x] = 1; nx[i][0] = (i + 1) % n; nx[i][1] = (i + n - 1) % n; } for (int d = 1; d < n; d++) { for (int l = 0, r = (l + d) % n; l < n; l++) { solve(l, (l + d) % n, 0); solve((l + d) % n, l, 1); } } pair<int, int> ans = {-1, 0}; for (int l = 0; l < n; l++) for (int r = 0; r < n; r++) for (int x = 0; x < 2; x++) ans = max(ans, make_pair(dp1[l][r][x], l + 1)); if (type) { for (int l = 0; l < n; l++) for (int r = 0; r < n; r++) for (int x = 0; x < 2; x++) { if (dp[l][r][x] <= 0) continue; int st = nx[r][x]; while (st != l && !edge[st][l]) st = nx[st][x]; if (st == l) continue; for (int ed = nx[st][x]; ed != l; ed = nx[ed][x]) { if (edge[r][ed]) { int num = max(dp1[ed][nx[st][x]][x ^ 1], dp1[ed][nx[l][x ^ 1]][x]); ans = max(ans, make_pair(1 + dp[l][r][x] + 1 + num, st + 1)); } } } } cout << ans.first << "\n" << ans.second << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...