Submission #1090324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090324		vjudge1	Sailing Race (CEOI12_race)	C++17	40 / 100	728 ms	6428 KiB

race

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define ar array

//const int INF = 1e17;
const int N = 600;
const int Q = 105;
const int MOD = 1e9 + 7;
const int LOG = 60;

int dp[N][N][2];
int n;
bool g[N][N];

int f(int l,int r,bool d){
    if(dp[l][r][d] != -1)return dp[l][r][d];
    int ans = 0;

    for(int i = (l + 1) % n;i != r;i = (i + 1) % n){
        int prv = d ? l : r; 
        if(g[prv][i]){
            ans = max(ans, f(l, i, 0) + 1);
            ans = max(ans, f(i,r,1) + 1);
        }
    }

    return dp[l][r][d] = ans;
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin>>n;
    int garb;
    cin>>garb;
    for(int i = 0;i < n;i++){
        int x;
        cin>>x;
        while(x){
            g[i][x - 1] = 1;
            cin>>x;
        }
    }
    int ans = 0;
    int mi = - 1;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(!g[i][j])continue;
            int res = f(i, j, 0) + 1;
            if(res > ans){
                ans = res;
                mi = i;
            }
            res = f(j, i, 1) + 1;
            if(res > ans){
                ans = res;
                mi = i;
            }
        }
    }
    cout<<ans<<" "<<mi + 1<<'\n';
}  


//! MI SE SPIEEEEE!

• Subtask 1: 40 / 100