Submission #1258827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258827		kunzaZa183	Sailing Race (CEOI12_race)	C++20	40 / 100	49 ms	5328 KiB

race

#include <bits/stdc++.h>
using namespace std;
const int mn = 500, vari = 5;
int dp[mn][mn][vari] = {};
vector<vector<int>> vvi;
int n, k;
bool ok(int l, int r, int num) {
  if (l > r)
    r += n;
  if (num < l)
    num += n;
  return (l < num && num < r);
}
int recur(int a, int b, bool type) {
  if (dp[a][b][type] != -1)
    return dp[a][b][type];

  int maxi = 0;
  if (type == 0) {
    for (auto to : vvi[a])
      if (ok(a, b, to)) {
        maxi = max({maxi, 1 + recur(a, to, 1), 1 + recur(to, b, 0)});
      }
  } else {
    for (auto to : vvi[b])
      if (ok(a, b, to)) {
        maxi = max({maxi, 1 + recur(a, to, 1), 1 + recur(to, b, 0)});
      }
  }

  return dp[a][b][type] = maxi;
}
int main() {
  cin >> n >> k;
  vvi.resize(n);
  for (int i = 0; i < n; i++) {
    while (1) {
      int x;
      cin >> x;
      if (x == 0)
        break;
      vvi[i].push_back(x - 1);
    }
  }

  if (k == 0) {
    // only use 2. 0 is from first number, 1 is from second number

    memset(dp, -1, sizeof dp);

    int maxi = 0, maxs = -1;

    for (int i = 0; i < n; i++) {
      for (auto a : vvi[i]) {
        if (1 + max(recur(a, i, 0), recur(i, a, 1)) > maxi) {
          maxi = 1 + max(recur(a, i, 0), recur(i, a, 1));
          maxs = i;
        }
      }
    }

    cout << maxi << "\n" << maxs + 1 << "\n";
  }
}

• Subtask 1: 40 / 100