제출 #1222674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222674		thewizardman	Sailing Race (CEOI12_race)	C++20	40 / 100	377 ms	5348 KiB

race

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define bruh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define N 501

int n, k;
pii dp[N][N][2], ans; // [l][r][end (at r -> true)]
int adj[N][N];

pii operator+(const pii& l, int r) {
  return {l.first +r, l.second};
}

int main() {
  bruh;
  cin >> n >> k;
  if (n == 1) { cout << 0; return 0; }
  if (n == 2) { cout << 1; return 0; }
  for (int u = 0; u < n; u++) {
    int v; while (cin >> v) {
      if (v == 0) break;
      adj[u][v-1] = 1;
    }
  }
  for (int i = 0; i < n; i++) dp[i][i][0] = dp[i][i][1] = {0, i+1};
  for (int len = 1; len < n; len++) for (int l = 0; l < n; l++) {
    int r = (l+len) % n;
    if (l < r) {
      // extend to r
      for (int k = l; k < r; k++) {
        if (adj[k][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][1] + 1);
        if (adj[l][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][0] + 1);
      }
      // extend to l
      for (int k = l+1; k <= r; k++) {
        if (adj[k][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][0] + 1);
        if (adj[r][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][1] + 1);
      }
    } else {
      // extend to r
      for (int k = l; k < n; k++) {
        if (adj[k][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][1] + 1);
        if (adj[l][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][0] + 1);
      }
      for (int k = 0; k < r; k++) {
        if (adj[k][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][1] + 1);
        if (adj[l][r]) dp[l][r][1] = max(dp[l][r][1], dp[l][k][0] + 1);
      }
      // extend to l
      for (int k = l+1; k < n; k++) {
        if (adj[k][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][0] + 1);
        if (adj[r][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][1] + 1);
      }
      for (int k = 0; k <= r; k++) {
        if (adj[k][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][0] + 1);
        if (adj[r][l]) dp[l][r][0] = max(dp[l][r][0], dp[k][r][1] + 1);
      }
    }
    ans = max({ans, dp[l][r][0], dp[l][r][1]});
  }
  cout << ans.first << '\n' << ans.second;
}

• Subtask 1: 40 / 100