#include <bits/stdc++.h>
using namespace std;
int n,c;
vector<int> muchii[505];
int dp[2][505][505]; // 0 -> cresc, 1 -> desc
int poz[505];
int ans,start=0;
bool use[505];
int main()
{
cin>>n>>c;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
while(x!=0)
{
muchii[i].push_back(x);
cin>>x;
}
}
for(int i=1;i<=n;i++)
dp[0][i][i]=dp[1][i][i]=0;
for(int lg=2;lg<n;lg++)
for(int i=1;i<=n;i++)
{
int dr=i;
for(int j=1;j<=n;j++)
use[j]=0;
for(int cnt=1;cnt<lg;cnt++)
{
use[dr]=1;
dr++;
use[dr]=1;
if(dr>n)
dr=1;
}
bool ok=0;
if(i==7&&dr==5)
ok=1;
dp[0][i][dr]=-1e9;
for(int j:muchii[i])
if(use[j])
{
int lft=i+1;
if(lft>n)
lft=1;
int rgt=j;
int val=dp[1][rgt][lft]+1;
dp[0][i][dr]=max(dp[0][i][dr],val);
lft=j;
rgt=dr;
val=dp[0][lft][rgt]+1;
dp[0][i][dr]=max(dp[0][i][dr],val);
}
int st=i;
for(int j=1;j<=n;j++)
use[j]=0;
for(int cnt=1;cnt<lg;cnt++)
{
use[st]=1;
st--;
use[st]=1;
if(st<1)
st=n;
}
dp[1][i][st]=-1e9;
for(int j:muchii[i])
if(use[j])
{
int rgt=i-1;
if(rgt<1)
rgt=n;
int lft=j;
int val=dp[0][lft][rgt]+1;
dp[1][i][st]=max(dp[1][i][st],val);
rgt=j;
lft=st;
val=dp[1][rgt][lft]+1;
dp[1][i][st]=max(dp[1][i][st],val);
}
if(dp[0][i][dr]>ans)
{
ans=dp[0][i][dr];
start=i;
}
if(dp[1][i][st]>ans)
{
ans=dp[1][i][st];
start=i;
}
}
cout<<ans<<' '<<start;
return 0;
}
Compilation message
race.cpp: In function 'int main()':
race.cpp:39:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
39 | bool ok=0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
7 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
8 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
9 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
10 |
Incorrect |
10 ms |
768 KB |
Output isn't correct |
11 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
12 |
Incorrect |
17 ms |
1108 KB |
Output isn't correct |
13 |
Incorrect |
40 ms |
1492 KB |
Output isn't correct |
14 |
Incorrect |
81 ms |
1936 KB |
Output isn't correct |
15 |
Incorrect |
187 ms |
2428 KB |
Output isn't correct |
16 |
Incorrect |
217 ms |
2524 KB |
Output isn't correct |
17 |
Incorrect |
182 ms |
2432 KB |
Output isn't correct |
18 |
Incorrect |
136 ms |
2348 KB |
Output isn't correct |
19 |
Incorrect |
229 ms |
2464 KB |
Output isn't correct |
20 |
Incorrect |
241 ms |
2536 KB |
Output isn't correct |