#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
//const ll mod = 1e9+7;
bool maximize(int &x, int y ){
if (x < y) {x = y; return true;};
return false;
}
bool minimize(int &x, int y){
if (x > y) {x = y; return true;}
return false;
}
//void add(ll &x, ll y ){
// x += y;
// if (x >= mod) x -= mod;
//}
//void sub(ll &x, ll y) {
// x -= y;
// if (x < 0) x += mod;
//}
const int maxn = 505;
int n, type;
bool a[maxn][maxn] = {0};
int dp[maxn][maxn][4] = {0}, ans = 0, s = 0;
int start[maxn][maxn][4];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> type;
for (int i = 1; i <= n; i++) {
int j;
while (cin >> j) {
if (j == 0) break;
a[i][j] = 1;
}
}
for (int l = 1; l <= n; l++) {
for (int i = 1; i <= n; i++) {
int j;
j = i-l+1;
if (j > 0) {
//dp1
if (a[i][j]) {
dp[i][j][0] = 1;
start[i][j][0] = i;
}
for (int k = j+1; k < i; k++) {
if (dp[i][k][0] && dp[k][j][0]) maximize(dp[i][j][0], dp[i][k][0]+dp[k][j][0]);
if (a[i][k]&&dp[k][j][2]) maximize(dp[i][j][1], dp[k][j][2]+1);
if (dp[i][k][1]&&dp[k][j][0]) maximize(dp[i][j][1], dp[i][k][1]+dp[k][j][0]);
}
if (maximize(ans, dp[i][j][0])) s = i;
if (type && maximize(ans, dp[i][j][1])) s = i;
}
else {
//dp2
j += n;
if (a[i][j]) {
dp[i][j][2] = 1;
start[i][j][2] = i;
}
for (int k = j+1; k != i; k=k%n+1) {
if (dp[i][k][2] && dp[k][j][2]) maximize(dp[i][j][2], dp[i][k][2]+dp[k][j][2]);
if (a[i][k]&&dp[k][j][0]) maximize(dp[i][j][3], dp[k][j][0]+1);
if (dp[i][k][3]&&dp[k][j][2]) maximize(dp[i][j][3], dp[i][k][3]+dp[k][j][2]);
}
if (maximize(ans, dp[i][j][2])) s = i;
if (type && maximize(ans, dp[i][j][3])) s = i;
}
j = i+l-1;
if (j <= n) {
if (a[i][j]) {
dp[i][j][0] = 1;
start[i][j][0] = i;
}
for (int k = i+1; k < j; k++) {
if (dp[i][k][0] && dp[k][j][0]) maximize(dp[i][j][0], dp[i][k][0]+dp[k][j][0]);
if (a[i][k]&&dp[k][j][2]) maximize(dp[i][j][1], dp[k][j][2]+1);
if (dp[i][k][1]&&dp[k][j][0]) maximize(dp[i][j][1], dp[i][k][1]+dp[k][j][0]);
}
if (maximize(ans, dp[i][j][0])) s = i;
if (type && maximize(ans, dp[i][j][1])) s = i;
}
else {
j -= n;
if (a[i][j]) {
dp[i][j][2] = 1;
start[i][j][2] = i;
}
for (int k = i+1; k != j; k=k%n+1) {
if (dp[i][k][2] && dp[k][j][2]) maximize(dp[i][j][2], dp[i][k][2]+dp[k][j][2]);
if (a[i][k]&&dp[k][j][0]) maximize(dp[i][j][3], dp[k][j][0]+1);
if (dp[i][k][3]&&dp[k][j][2]) maximize(dp[i][j][3], dp[i][k][3]+dp[k][j][2]);
}
if (maximize(ans, dp[i][j][2])) s = i;
if (type && maximize(ans, dp[i][j][3])) s = i;
}
}
}
cout << ans << "\n" << s;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
2908 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
3104 KB |
Output isn't correct |
| 9 |
Incorrect |
7 ms |
3164 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
3164 KB |
Output isn't correct |
| 11 |
Incorrect |
11 ms |
3164 KB |
Output isn't correct |
| 12 |
Incorrect |
55 ms |
4188 KB |
Output isn't correct |
| 13 |
Incorrect |
166 ms |
5212 KB |
Output isn't correct |
| 14 |
Incorrect |
381 ms |
7008 KB |
Output isn't correct |
| 15 |
Incorrect |
760 ms |
8536 KB |
Output isn't correct |
| 16 |
Incorrect |
783 ms |
8540 KB |
Output isn't correct |
| 17 |
Incorrect |
709 ms |
8712 KB |
Output isn't correct |
| 18 |
Incorrect |
721 ms |
8528 KB |
Output isn't correct |
| 19 |
Incorrect |
788 ms |
8704 KB |
Output isn't correct |
| 20 |
Incorrect |
778 ms |
8536 KB |
Output isn't correct |
