Submission #1090359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090359		vjudge1	Sailing Race (CEOI12_race)	C++17	40 / 100	709 ms	3664 KiB

race

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

int dp[505][505][2], mat[505][505], n, shit;

int f(int l, int r, int t) {
    if(dp[l][r][t] != -1) return dp[l][r][t];

    int ans = 0, p = (t ? l : r);
    for(int i=(l+1)%n; i!=r; i=(i+1)%n) {
        if(!mat[p][i]) continue;
        ans = max(ans, max(f(l, i, 0), f(i, r, 1)) + 1);
    }

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

signed main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> shit;

    for(int i=0; i<n; i++) {
        int x;
        while(cin >> x) {
            if(!x) break;
            mat[i][x-1] = 1;
        }
    }

    int ans=-1, pos=-1;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(!mat[i][j]) continue;
            int res = max(f(i, j, 0), f(j, i, 1)) + 1;
            if(res > ans) {
                ans = res;
                pos = i + 1;
            }
        }
    }

    cout << ans << " " << pos << '\n';
    return 0;
}

• Subtask 1: 40 / 100