oj.uz

Submission #1091095

# Submission time Handle Problem Language Result Execution time Memory
1091095 2024-09-19T19:00:43 Z vjudge1 Sailing Race (CEOI12_race) C++17
40 / 100
 654 ms 2796 KB 
#include <bits/stdc++.h>
using namespace std;
bool g[501][501];
int dp[501][501][2];
int n;
void najdi(int l,int r,int i)
{
    if(dp[l][r][i]!=-1)return;
    int d=r;
    if(i==1)
    {
        d=l;
    }
    int res=0;
    for(int j=(l+1)%n;j!=r;j=(j+1)%n)
    {
        if(g[d][j])
        {
            najdi(l,j,0);
            najdi(j,r,1);
            res=max(res,1+max(dp[l][j][0],dp[j][r][1]));
        }
    }
    dp[l][r][i]=res;
}
int main()
{
    int k;
    cin>>n>>k;
    int ans=0,res=0,x=0;
    for(int i=0;i<n;i++)
    {
        int a;
        for(int j=0;j<n;j++)
        {
            dp[i][j][0]=-1;
            dp[i][j][1]=-1;
        }
        while(cin>>a&&a!=0)
        {
            g[i][a-1]=1;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(g[i][j])
            {
                najdi(i,j,0);
                najdi(j,i,1);
                res=max(res,1+max(dp[i][j][0],dp[j][i][1]));
                if(res>ans)
                {
                    x=i;
                    ans=res;
                }
            }
        }
    }
    cout<<ans<<endl<<x+1;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 356 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Correct 1 ms 608 KB Output is correct
6 Incorrect 2 ms 608 KB Output isn't correct
7 Correct 3 ms 608 KB Output is correct
8 Incorrect 2 ms 604 KB Output isn't correct
9 Correct 5 ms 608 KB Output is correct
10 Correct 7 ms 860 KB Output is correct
11 Correct 7 ms 856 KB Output is correct
12 Incorrect 39 ms 1116 KB Output isn't correct
13 Incorrect 107 ms 1628 KB Output isn't correct
14 Correct 234 ms 2220 KB Output is correct
15 Incorrect 583 ms 2648 KB Output isn't correct
16 Incorrect 623 ms 2772 KB Output isn't correct
17 Incorrect 593 ms 2732 KB Output isn't correct
18 Correct 398 ms 2652 KB Output is correct
19 Incorrect 654 ms 2648 KB Output isn't correct
20 Incorrect 651 ms 2796 KB Output isn't correct