Submission #1222674

#TimeUsernameProblemLanguageResultExecution timeMemory
1222674thewizardmanSailing Race (CEOI12_race)C++20
40 / 100
377 ms5348 KiB
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define bruh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define N 501 int n, k; pii dp[N][N][2], ans; // [l][r][end (at r -> true)] int adj[N][N]; pii operator+(const pii& l, int r) { return {l.first +r, l.second}; } int main() { bruh; cin >> n >> k; if (n == 1) { cout << 0; return 0; } if (n == 2) { cout << 1; return 0; } for (int u = 0; u < n; u++) { int v; while (cin >> v) { if (v == 0) break; adj[u][v-1] = 1; } } for (int i = 0; i < n; i++) dp[i][i][0] = dp[i][i][1] = {0, i+1}; for (int len = 1; len < n; len++) for (int l = 0; l < n; l++) { int r = (l+len) % n; if (l < r) { // extend to r for (int k = l; k < r; k++) { if (adj[k][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][1] + 1); if (adj[l][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][0] + 1); } // extend to l for (int k = l+1; k <= r; k++) { if (adj[k][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][0] + 1); if (adj[r][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][1] + 1); } } else { // extend to r for (int k = l; k < n; k++) { if (adj[k][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][1] + 1); if (adj[l][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][0] + 1); } for (int k = 0; k < r; k++) { if (adj[k][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][1] + 1); if (adj[l][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][0] + 1); } // extend to l for (int k = l+1; k < n; k++) { if (adj[k][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][0] + 1); if (adj[r][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][1] + 1); } for (int k = 0; k <= r; k++) { if (adj[k][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][0] + 1); if (adj[r][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][1] + 1); } } ans = max({ans, dp[l][r][0], dp[l][r][1]}); } cout << ans.first << '\n' << ans.second; }
#Verdict Execution timeMemoryGrader output
Fetching results...