Submission #832281

#TimeUsernameProblemLanguageResultExecution timeMemory
832281TS_2392Sailing Race (CEOI12_race)C++14
0 / 100
1107 ms5296 KiB
#include <bits/stdc++.h> using namespace std; #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);} #define SPEED {ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);} template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;} template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;} const int N = 503; int n, type, res, nxt[N], prv[N]; int adj[N][N], dp1[N][N][2], dp2[N][N][2]; int main(){ cin >> n >> type; for(int u = 1, v; u <= n; ++u){ while(cin >> v){ if(v == 0) break; else adj[u][v] = 1; } nxt[u] = u + 1; prv[u] = u - 1; } nxt[n] = 1; prv[1] = n; for(int len = 2; len < n; ++len){ for(int i = 1; i <= n; ++i){ int j = i + len - 1; if(j > n) j -= n; if(adj[i][j]) dp1[i][j][0] = 1; for(int k = nxt[i]; k != j; k = nxt[k]) if(adj[k][j] && dp1[i][k][0]){ maximize(dp1[i][j][0], dp1[i][k][0] + 1); } if(adj[j][i]) dp1[i][j][1] = 1; for(int k = prv[j]; k != i; k = prv[k]) if(adj[k][i] && dp1[k][j][1]){ maximize(dp1[i][j][1], dp1[k][j][1] + 1); } } } for(int len = 2; len < n; ++len){ for(int i = 1; i <= n; ++i){ int j = i + len - 1; if(j > n) j -= n; dp2[i][j][0] = dp2[i][prv[j]][0]; if(adj[i][j]) maximize(dp2[i][j][0], dp2[nxt[i]][j][1] + 1); for(int k = nxt[i]; k != j; k = nxt[k]) if(adj[k][j] && dp1[i][k][0]){ maximize(dp2[i][j][0], dp1[i][k][0] + 1 + dp2[nxt[k]][j][1]); } dp2[i][j][1] = dp2[nxt[i]][j][1]; if(adj[j][i]) maximize(dp2[i][j][1], dp2[i][prv[j]][0] + 1); for(int k = prv[j]; k != i; k = prv[k]) if(adj[k][i] && dp1[k][j][1]){ maximize(dp2[i][j][1], dp1[k][j][1] + 1 + dp2[i][prv[k]][0]); } maximize(res, dp2[i][j][0]); maximize(res, dp2[i][j][1]); } } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...