#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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
0 ms |
468 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
724 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
3 ms |
796 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
980 KB |
Output isn't correct |
| 8 |
Incorrect |
5 ms |
1108 KB |
Output isn't correct |
| 9 |
Incorrect |
11 ms |
1108 KB |
Output isn't correct |
| 10 |
Incorrect |
9 ms |
1288 KB |
Output isn't correct |
| 11 |
Incorrect |
14 ms |
1292 KB |
Output isn't correct |
| 12 |
Incorrect |
64 ms |
2268 KB |
Output isn't correct |
| 13 |
Incorrect |
184 ms |
3248 KB |
Output isn't correct |
| 14 |
Incorrect |
370 ms |
4240 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
856 ms |
5168 KB |
Output isn't correct |
| 16 |
Incorrect |
946 ms |
5216 KB |
Output isn't correct |
| 17 |
Incorrect |
878 ms |
5220 KB |
Output isn't correct |
| 18 |
Incorrect |
645 ms |
5172 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
1107 ms |
5212 KB |
Output isn't correct |
| 20 |
Incorrect |
1016 ms |
5296 KB |
Output isn't correct |
