Submission #1174344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174344		vincentbucourt1	Sailing Race (CEOI12_race)	C++20	10 / 100	344 ms	5036 KiB

race

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long

const int MAXN = 520;

int N, type;
vector<int> adj[MAXN];
int dp[MAXN][MAXN][2];

int dist (int n1, int n2, int d) {
    return ((n2 - n1) / d + N*N) % N;
}
bool between (int n1, int n2, int n3, int d) {
    return (dist(n1, n2, d) + dist(n2, n3, d) == dist(n1, n3, d));
}

signed main() {
    fastIO();
    cin >> N >> type;
    for (int i = 0; i < N; i++) {
        int on;
        cin >> on;
        while (on != 0) {
            if (i != on-1) {
                adj[i].push_back(on-1);
            }
            cin >> on;
        }
    }
    for (int len = 1; len < N; len++) {
        for (int node = 0; node < N; node++) {
            for (int mid : adj[node]) {
                int other = (node + len) % N;
                if (between(node, mid, other, 1)) {
                    dp[node][other][1] = max(dp[node][other][1], dp[mid][(node+1)%N][0] + dp[mid][other][1] + 1);
                }
                other = (node - len + N) % N;
                if (between(node, mid, other, -1)) {
                    dp[node][other][0] = max(dp[node][other][0], dp[mid][(node-1+N)%N][1] + dp[mid][other][0] + 1);
                }
            }
        }
    }
    assert(type == 0);
    if (type == 0) {
        int ans = 0, iAns = 0;
        for (int i = 0; i < N; i++) {
            if (ans < dp[i][(i+1)%N][0]) {
                ans = dp[i][(i+1)%N][0];
                iAns = i;
            }
        }
        cout << ans << "\n" << iAns+1 << "\n";
        return 0;
    }
}

• Subtask 1: 10 / 100