Submission #1146200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146200		Trisanu_Das	Sailing Race (CEOI12_race)	C++20	40 / 100	413 ms	4632 KiB

race

#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 505;
bool adj[N][N];
int vis[N][N][2], dp[N][N][2];

int f(int a, int b, int dir) {
    bool t = (dir == a);
    if(vis[a][b][t]) return dp[a][b][t];
    int ans = 0;
    for(int i = a + 1; i != b; i++) {
        if(i == n) i = 0;
        if(i == b) break;
        if(adj[dir][i]) {
            ans = max(ans, f(a, i, i) + 1);
            ans = max(ans, f(i, b, i) + 1);
        }
    }
    vis[a][b][t] = true;
    dp[a][b][t] = ans;
    return ans;
}

signed main() {
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        int x;
        while(cin >> x) {
            if(!x)break;
            x--;
            adj[i][x] = true;
        }
    }
    int pos,ans = 0;
    for(int i = 0; i < n; i++) {
        int tmp = f(i, i, i);
        if(tmp > ans) {
            ans = tmp;
            pos = i;
        }
    }
    cout << ans << '\n' << pos + 1 << '\n';
}

• Subtask 1: 40 / 100