#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 = 2; 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 ((a[i][j]&&dp[k][i][2])&&maximize(dp[i][j][0], dp[k][i][2]+1)) {
start[i][j][0] = start[k][i][2];
}
if ((dp[i][k][0] && dp[k][j][0])&&maximize(dp[i][j][0], dp[i][k][0]+dp[k][j][0])) {
start[i][j][0] = start[i][k][0];
}
if ((a[i][k]&&dp[k][j][2])&&maximize(dp[i][j][1], dp[k][j][2]+1)) {
start[i][j][1] = i;
}
if ((dp[i][k][1]&&dp[k][j][0])&&maximize(dp[i][j][1], dp[i][k][1]+dp[k][j][0])) {
start[i][j][1] = start[i][k][1];
}
}
if (maximize(ans, dp[i][j][0])) s = start[i][j][0];
if (type && maximize(ans, dp[i][j][1])) s = start[i][j][1];
// cout << i << ' ' << j << " 01 " << dp[i][j][0] << ' ' << dp[i][j][1] << "\n";
// cout << i << ' ' << j << " 01 " << start[i][j][0] << ' ' << start[i][j][1] << "\n";
}
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 ((a[i][j]&&dp[k][i][0])&&maximize(dp[i][j][2], dp[k][i][0]+1)) {
start[i][j][2] = start[k][i][0];
}
if ((dp[i][k][2] && dp[k][j][2])&&maximize(dp[i][j][2], dp[i][k][2]+dp[k][j][2])) {
start[i][j][2] = start[i][k][2];
}
if ((a[i][k]&&dp[k][j][0])&&maximize(dp[i][j][3], dp[k][j][0]+1)) {
start[i][j][3] = i;
}
if ((dp[i][k][3]&&dp[k][j][2])&&maximize(dp[i][j][3], dp[i][k][3]+dp[k][j][2])) {
start[i][j][3] = start[i][k][3];
}
}
if (maximize(ans, dp[i][j][2])) s = start[i][j][2];
if (type && maximize(ans, dp[i][j][3])) s = start[i][j][3];
// cout << i << ' ' << j << " 23 " << dp[i][j][2] << ' ' << dp[i][j][3] << "\n";
// cout << i << ' ' << j << " 23 " << start[i][j][2] << ' ' << start[i][j][3] << "\n";
}
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 ((a[i][j]&&dp[k][i][2])&&maximize(dp[i][j][0], dp[k][i][2]+1)) {
start[i][j][0] = start[k][i][2];
}
if ((dp[i][k][0] && dp[k][j][0])&&maximize(dp[i][j][0], dp[i][k][0]+dp[k][j][0])) {
start[i][j][0] = start[i][k][0];
}
if ((a[i][k]&&dp[k][j][2])&&maximize(dp[i][j][1], dp[k][j][2]+1)) {
start[i][j][1] = i;
}
if ((dp[i][k][1]&&dp[k][j][0])&&maximize(dp[i][j][1], dp[i][k][1]+dp[k][j][0])) {
start[i][j][1] = start[i][k][1];
}
}
if (maximize(ans, dp[i][j][0])) s = start[i][j][0];
if (type && maximize(ans, dp[i][j][1])) s = start[i][j][1];
// cout << i << ' ' << j << " 01 " << dp[i][j][0] << ' ' << dp[i][j][1] << "\n";
// cout << i << ' ' << j << " 01 " << start[i][j][0] << ' ' << start[i][j][1] << "\n";
}
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 ((a[i][j]&&dp[k][i][0])&&maximize(dp[i][j][2], dp[k][i][0]+1)) {
start[i][j][2] = start[k][i][0];
}
if ((dp[i][k][2] && dp[k][j][2])&&maximize(dp[i][j][2], dp[i][k][2]+dp[k][j][2])) {
start[i][j][2] = start[i][k][2];
}
if ((a[i][k]&&dp[k][j][0])&&maximize(dp[i][j][3], dp[k][j][0]+1)) {
start[i][j][3] = i;
}
if ((dp[i][k][3]&&dp[k][j][2])&&maximize(dp[i][j][3], dp[i][k][3]+dp[k][j][2])) {
start[i][j][3] = start[i][k][3];
}
}
if (maximize(ans, dp[i][j][2])) s = start[i][j][2];
if (type && maximize(ans, dp[i][j][3])) s = start[i][j][3];
// cout << i << ' ' << j << " 23 " << dp[i][j][2] << ' ' << dp[i][j][3] << "\n";
// cout << i << ' ' << j << " 23 " << start[i][j][2] << ' ' << start[i][j][3] << "\n";
}
}
}
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 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
2648 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
2908 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
2908 KB |
Output isn't correct |
| 8 |
Incorrect |
5 ms |
2960 KB |
Output isn't correct |
| 9 |
Incorrect |
8 ms |
3164 KB |
Output isn't correct |
| 10 |
Incorrect |
8 ms |
3164 KB |
Output isn't correct |
| 11 |
Incorrect |
11 ms |
3164 KB |
Output isn't correct |
| 12 |
Incorrect |
59 ms |
4188 KB |
Output isn't correct |
| 13 |
Incorrect |
169 ms |
5212 KB |
Output isn't correct |
| 14 |
Incorrect |
392 ms |
7008 KB |
Output isn't correct |
| 15 |
Incorrect |
782 ms |
8532 KB |
Output isn't correct |
| 16 |
Incorrect |
762 ms |
8620 KB |
Output isn't correct |
| 17 |
Incorrect |
748 ms |
8536 KB |
Output isn't correct |
| 18 |
Incorrect |
724 ms |
8592 KB |
Output isn't correct |
| 19 |
Incorrect |
814 ms |
8528 KB |
Output isn't correct |
| 20 |
Incorrect |
828 ms |
8696 KB |
Output isn't correct |
